F - Smaller.cpp

#include <bits/stdc++.h>

using namespace std;

int T, q, d, k;
string x;
long long int cnt[26], t[26], s[26], tmp_t[26], tmp_s[26];

bool test(){
    int p1 = 0, p2 = 25;
    for(int i = 0; i < 26; i++){
        tmp_t[i] = t[i], tmp_s[i] = s[i];
    }
    while(1){
        while(p1 < 26 && tmp_s[p1] == 0) p1++;
        while(p2 >= 0 && tmp_t[p2] == 0) p2--;
        if(p2 == -1) return false;
        if(p1 == 26) return true;

        if(p1 < p2) return true;
        if(p1 > p2) return false;

        long long int val = min(tmp_s[p1], tmp_t[p2]);
        tmp_s[p1] -= val, tmp_t[p2] -= val;
    }
}

int main(){
    cin.tie(nullptr), ios::sync_with_stdio(false);
    cin >> T;
    while(T--){
        for(int i = 0; i < 26; i++) s[i] = t[i] = 0;
        s[0] = t[0] = 1;

        cin >> q;
        while(q--){
            cin >> d >> k >> x;
            for(int i = 0; i < 26; i++) cnt[i] = 0;
            for(char c : x) cnt[c - 'a']++;
            for(int i = 0; i < 26; i++){
                if(d == 1) s[i] += cnt[i] * k;
                else t[i] += cnt[i] * k;
            }

            cout << (test() ? "YES\n" : "NO\n");
        }
    }
}