Submission #1186116

#TimeUsernameProblemLanguageResultExecution timeMemory
1186116GrayCrossing (JOI21_crossing)C++20
26 / 100
148 ms20716 KiB
#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;
    string s, _; cin >> s >> _ >> _;
    ll q; cin >> q;
    string t; cin >> t;
    SegTree tr(n); tr.build(s, t);
    cout << (tr.query()?"Yes\n":"No\n");
    while (q--){
        ll l, r; char x; cin >> l >> r >> x;
        tr.update(l-1, r-1, x);
        cout << (tr.query()?"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
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...