Submission #1186130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186130		Gray	Crossing (JOI21_crossing)	C++20	100 / 100	4367 ms	414780 KiB

Main

#include <algorithm>
#include <bits/stdc++.h>
#include <ios>
using namespace std;

#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD (ll)(1e9+7)

struct SegTree{
    struct node{
        ll match, same; char act, cur, upd;
        node(){
            match=same=1; act=cur=upd=0;
        }
        node(ll match, ll same, char act, char cur):match(match),same(same),act(act),cur(cur){
            upd=0;
        }
    };
    vector<node> t; ll sz, rsz;
    SegTree(ll N){
        sz=N*4; rsz=N; t.resize(sz);
    }
    node merge(node l, node r){
        return node(l.match&r.match, (l.same and r.same and l.act==r.act), l.act, l.cur);
    }
    void preprocess(ll tl, ll tr, ll v){
        if (t[v].upd){
            if (t[v].same){
                t[v].match = (t[v].act==t[v].upd);
                t[v].cur=t[v].upd;
            }else{
                t[v].match = 0;
                t[v].cur=t[v].upd;
            }
            if (tl!=tr){
                t[v*2].upd=t[v].upd;
                t[v*2+1].upd=t[v].upd;
            }
            t[v].upd=0;
        }
    }
    void build(ll tl, ll tr, ll v, string &s, string &a){
        if (tl==tr){
            t[v].same=1; t[v].match=(s[tl]==a[tl]);
            t[v].act=s[tl]; t[v].cur=a[tl];
        }else{
            ll tm = (tl+tr)/2;
            build(tl, tm, v*2, s, a);
            build(tm+1, tr, v*2+1, s, a);
            t[v] = merge(t[v*2], t[v*2+1]);
        }
    }
    void build(string &s, string &a){
        build(0, rsz-1, 1, s, a);
    }
    void update(ll tl, ll tr, ll v, ll l, ll r, char x){
        preprocess(tl, tr, v);
        if (tl==l and tr==r){
            t[v].upd=x; preprocess(tl, tr, v);
        }else if (l>r) return;
        else {
            ll tm = (tl+tr)/2;
            update(tl, tm, v*2, l, min(r, tm), x);
            update(tm+1, tr, v*2+1, max(l, tm+1), r, x);
            t[v]=merge(t[v*2], t[v*2+1]);
        }
    }
    void update(ll l, ll r, char x){
        update(0, rsz-1, 1, l, r, x);
    }
    bool query(){
        return t[1].match;
    }
};

void solve(){
    ll n; cin >> n;
    vector<string> s(3); cin >> s[0] >> s[1] >> s[2];
    ll q; cin >> q;
    string t; cin >> t;
    vector<vector<SegTree>> tr(6, vector<SegTree>(3, SegTree(n)));
    vector<ll> perm = {0, 1, 2}; ll ord=0;
    do{
        string cur="";
        for (auto j:perm){
            if (cur.empty()) cur=s[j];
            else{
                for (ll k=0; k<n; k++){
                    if (cur[k]!=s[j][k]){
                        cur[k]=cur[k]^s[j][k]^'J'^'O'^'I';
                    }
                }
            }
            tr[ord][j].build(cur, t);
        }
        ord++;
    }while (next_permutation(perm.begin(), perm.end()));

    bool pos=0;
    for (ll i=0; i<6; i++){
        for (ll j=0; j<3; j++) if (tr[i][j].query()) pos=1;
    }
    cout << (pos?"Yes\n":"No\n");
    while (q--){
        ll l, r; char x; cin >> l >> r >> x;
        pos=0;
        for (ll i=0; i<6; i++){
            for (ll j=0; j<3; j++){
                tr[i][j].update(l-1, r-1, x);
                if (tr[i][j].query()) pos=1;
            }
        }
        cout << (pos?"Yes\n":"No\n");
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    for (ll __c=1; __c<=t; __c++) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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