CSES - HIIT Open 2016 - Results
Submission details
Task:HIIT remains
Sender:Anonyymit Algoritmistit
Submission time:2016-05-28 12:20:52 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.05 sdetails
#2ACCEPTED0.06 sdetails
#3ACCEPTED0.07 sdetails
#4ACCEPTED0.05 sdetails

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  
  ll t;
  cin >> t;
  
  for(int x = 0; x < t; x++) {
    
    string s;
    cin >> s;
    ll n = s.length();
    
    vector<ll> hiit;
    vector<ll> iit;
    vector<ll> it;
    vector<ll> t;
    
    hiit.resize(n);
    iit.resize(n);
    it.resize(n);
    t.resize(n);
    
    if (s[n-1] == 'T') t[n-1]++;
      
    for(int j = n-2; j >= 0; j--) {
      t[j]+=t[j+1];
      
      if (s[j] == 'T') {
	t[j]++;
      }
      
    }
    
    for(int j = n-2; j >= 0; j--) {
      it[j] += it[j+1];
      if (s[j] == 'I') {
	it[j] += t[j+1];
      }
      
    }
    
    for(int j = n-2; j >= 0; j--) {
      iit[j] += iit[j+1];
      if (s[j] == 'I') {
	iit[j] += it[j+1];
      }
    }
    
    for(int j = n-2; j >= 0; j--) {
      hiit[j] += hiit[j+1];
      if (s[j] == 'H') {
	hiit[j] += iit[j+1];
      }
    }
    /*for(int i = 0; i < n; i++) {
      cout << hiit[i] << " ";
    }*/
    
    //cout << endl;
    cout << hiit[0] << endl;
  }
  
}

Test details

Test 1

Verdict: ACCEPTED

input
100
IIITIIIHITHTHIIITIII
HIHIIIIIIHIIITHIIIII
ITTIIIITIIIIIIITIIIT
IITHITITIHHIITTTIIII
...

correct output
12
84
0
37
96
...

user output
12
84
0
37
96
...

Test 2

Verdict: ACCEPTED

input
100
TIIHHITTITITIHTHIIIITHIHHIIHTI...

correct output
606723862
621369559
655243897
550750615
717769300
...

user output
606723862
621369559
655243897
550750615
717769300
...

Test 3

Verdict: ACCEPTED

input
10
TTHTHHTIIIIIITHIIHIITITTITTIIH...

correct output
64668032062669502
66159978956790306
65755072918424640
64408596558953628
65238005187079543
...

user output
64668032062669502
66159978956790306
65755072918424640
64408596558953628
65238005187079543
...

Test 4

Verdict: ACCEPTED

input
3
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHH...

correct output
781234375000000000
4999750003
0

user output
781234375000000000
4999750003
0