Submission #1127431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127431		vladilius	Crossing (JOI21_crossing)	C++20	100 / 100	5088 ms	125548 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>

struct DS{
    string a;
    vector<int> rr;
    int n, cc;
    set<pair<pii, char>> st;
    void init(string as, string b){
        a = as;
        n = (int) a.size();
        cc = 0;
        for (int i = 0; i < n; i++){
            st.insert({{i, i}, b[i]});
            cc += (b[i] != a[i]);
        }
        rr.resize(n);
        int i = 0;
        while (i < n){
            int j = i;
            while (j < n && a[i] == a[j]){
                j++;
            }
            j--;
            while (i <= j){
                rr[i++] = j;
            }
        }
    }
    bool val(int l, int r, char x){ 
        return (rr[l] >= r && a[l] == x);
    }
    void upd(int l, int r, char x){
        auto it = st.lower_bound({{l + 1, 0}, 0}); it--;
        auto [p, y] = (*it);
        if (p.ff < l){
            cc -= !val(p.ff, p.ss, y);
            st.erase(it);
            
            st.insert({{p.ff, l - 1}, y});
            st.insert({{l, p.ss}, y});
            
            cc += !val(p.ff, l - 1, y);
            cc += !val(l, p.ss, y);
        }
        
        it = st.upper_bound({{r + 1, 0}, 0}); it--;
        p = (*it).ff; y = (*it).ss;
        if (r < p.ss){
            cc -= !val(p.ff, p.ss, y);
            st.erase(it);
            
            st.insert({{p.ff, r}, y});
            st.insert({{r + 1, p.ss}, y});
            
            cc += !val(p.ff, r, y);
            cc += !val(r + 1, p.ss, y);
        }
        
        while (true){
            it = st.lower_bound({{l, 0}, 0});
            if (it == st.end() || (*it).ff.ff > r) break;
            
            auto [p, y] = (*it);
            
            cc -= !val(p.ff, p.ss, y);
            st.erase(it);
        }
        
        st.insert({{l, r}, x});
        cc += !val(l, r, x);
    }
    bool get(){
        return !cc;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n; cin>>n;
    string a, b, c; cin>>a>>b>>c;

    vector<char> C = {'J', 'O', 'I'};
    
    auto f = [&](string x, string y){
        string t;
        for (int i = 0; i < n; i++){
            if (x[i] == y[i]){
                t += x[i];
                continue;
            }
            for (char s: C){
                if (s != x[i] && s != y[i]){
                    t += s;
                    break;
                }
            }
        }
        return t;
    };
    
    vector<string> all = {a, b, c, f(a, b), f(b, c), f(a, c), f(f(a, b), c), f(f(b, c), a), f(f(a, c), b)};

    int q; cin>>q;
    string t; cin>>t;
    
    DS T[9];
    for (int i = 0; i < 9; i++){
        T[i].init(all[i], t);
    }
    
    auto check = [&](string s){
        for (int i = 0; i < 9; i++){
            if (T[i].get()){
                cout<<"Yes"<<"\n";
                return;
            }
        }
        cout<<"No"<<"\n";
        return;
    };
    
    check(t);
    
    while (q--){
        int l, r; char S; cin>>l>>r>>S;
        l--; r--;
        for (int i = 0; i < 9; i++){
            T[i].upd(l, r, S);
        }
        check(t);
    }
}

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51