Submission #531946

#	Time	Username	Problem	Language	Result	Execution time	Memory
531946		GrandTiger1729	Crossing (JOI21_crossing)	C++17	0 / 100	68 ms	5488 KiB

Main

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

vector<string> s(3);
vector<long long> hash_val(9);
string q;

long long c[(int)2e5+1], cc[(int)(2e5+2)];
const int mod=1e9+7;

void get(string &a, string &b){
    string res;
    int n=a.size();
    for (int i=0; i<n; i++){
        if (a[i] == b[i]){
            res += a[i]; continue;
        }
        if (a[i] == 'J'){
            if (b[i] == 'O'){res += 'I';}
            else{res += 'O';}
        }else if (a[i] == 'O'){
            if (b[i] == 'J'){res += 'I';}
            else{res += 'J';}
        }else{
            if (b[i] == 'J'){res += 'O';}
            else{res += 'J';}
        }
    }
    s.push_back(res);
}

long long get_hash(string &a){
    int n=a.size();
    long long res=0;
    for (int i=0; i<n; i++){
        res += c[i] * (a[i]-'A');
        res %= mod;
    }
    return res;
}

struct segTree{
    int l, r, mid;
    long long val, lz=0;
    segTree *tl, *tr;
    segTree(int ll, int rr): l(ll), r(rr){
        mid = (l+r)/2;
        if (l == r-1){
            val = c[l] * (q[l]-'A');
            return;
        }
        tl = new segTree(l, mid);
        tr = new segTree(mid, r);
        val = (tl->val + tr->val) % mod;
    }
    void push(){
        if (lz == 0){return;}
        if (l == r-1){
            val = c[l] * lz % mod; lz = 0;
            return;
        }
        tl->val = lz * (cc[mid] - cc[l]) % mod;
        tr->val = lz * (cc[r] - cc[mid]) % mod;
        tl->lz = lz; tr->lz = lz;
        lz = 0;
    }
    void update(int ll, int rr, long long u){
        if (ll <= l && rr >= r){
            lz = u;
            val = u * (cc[r] - cc[l]);
            val %= mod;
            if (val < 0){val += mod;}
            return;
        }
        push();
        if (ll < mid){tl->update(ll, rr, u);}
        if (mid < rr){tr->update(ll, rr, u);}
        val = tl->val + tr->val;
    }
};

int main(){
    cin.sync_with_stdio(0); cin.tie(0);
    int len; cin >> len;
    for (int i=0; i<3; i++){cin >> s[i];}
    get(s[0], s[1]); get(s[1], s[2]); get(s[2], s[0]);
    get(s[3], s[2]); get(s[4], s[0]); get(s[5], s[1]);
    c[0] = 1;
    for (int i=1; i<2e5+1; i++){
        c[i] = c[i-1] * 29;
        c[i] %= mod;
    }
    cc[0] = 0;
    for (int i=1; i<2e5+2; i++){
        cc[i] = cc[i-1] + c[i-1];
        cc[i] %= mod;
    }
    for (int i=0; i<9; i++){
        hash_val[i] = get_hash(s[i]);
    }
    int n; cin >> n;
    cin >> q;
    segTree st(0, len);
    bool check=0;
    for (auto v: hash_val){
        if (v == st.val){check = 1; break;}
    }
    cout << ((check)? "Yes": "No") << '\n';
    for (int nn=0; nn<n; nn++){
        int l, r; char m; cin >> l >> r >> m;
        int x=m-'A'; l--;
        st.update(l, r, x);
        check = 0;
        for (auto v: hash_val){
            if (v == st.val){check = 1; break;}
        }
        cout << ((check)? "Yes": "No") << '\n';
    }
    return 0;
}

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