HIIT remains

#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 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED