HIIT remains

#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <set>
 
int main()
{
	int t;
	std::cin >> t;
	for (int ti = 0; ti < t; ++ti) {
		std::string s;
		std::cin >> s;
		std::vector<int> H;
		std::vector<int> I;
		std::vector<int> T;
		for (int i = 0; i < int(s.size()); ++i) {
			auto c = s[i];
			if (c == 'H') H.push_back(i);
			if (c == 'I') I.push_back(i);
			if (c == 'T') T.push_back(i);
		}
 
		if (H.size() == 0 || T.size() == 0) {
			std::cout << 0 << std::endl;
			continue;
		}
 
		int Hmin = H[0];
		int Tmax = T[T.size() - 1];
		std::vector<int> Iok;
		for (auto i : I) {
			if (i < Hmin) continue;
			if (i > Tmax) break;
			Iok.push_back(i);
		}
 
		if (Iok.size() < 2) {
			std::cout << 0 << std::endl;
			continue;
		}
 
		std::vector<long long> Hbefore(Iok.size(), 0);
		std::vector<long long> Tafter(Iok.size(), 0);
 
		int Hi = 0; // num of H values before this I
		int Ti = 0; // num of T values before this I
		for (int iI = 0; iI < int(Iok.size()); ++iI) {
			int i = Iok[iI];
			while (Hi < int(H.size()) && H[Hi] < i) Hi++;
			Hbefore[iI] = Hi;
 
			while (Ti < int(T.size()) && T[Ti] < i) Ti++;
			Tafter[iI] = T.size() - Ti;
		}
 
		std::vector<long long> TafterCumu(Iok.size());
		TafterCumu[Iok.size() - 1] = Tafter[Iok.size() - 1];
		for (int iI = int(Iok.size()) - 2; iI >= 0; --iI) {
			TafterCumu[iI] = Tafter[iI] + TafterCumu[iI+1];
		}
 
		// std::cerr << "Hbefore:";
		// for (auto h : Hbefore) std::cerr << " " << h;
		// std::cerr << std::endl;
		// std::cerr << "Iok:";
		// for (auto h : Iok) std::cerr << " " << h;
		// std::cerr << std::endl;
		// std::cerr << "Tafter:";
		// for (auto h : Tafter) std::cerr << " " << h;
		// std::cerr << std::endl;
		// std::cerr << "TafterCumu:";
		// for (auto h : TafterCumu) std::cerr << " " << h;
		// std::cerr << std::endl;
 
		long long count = 0;
		for (int iI = 0; iI < (int(Iok.size()) - 1); ++iI) {
			count += Hbefore[iI] * TafterCumu[iI + 1];
		}
 
		std::cout << count << std::endl;
	}
}
 

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED