Submission #1255532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255532		damoon	Crossing (JOI21_crossing)	C++20	100 / 100	515 ms	29264 KiB

Main

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

#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define unicorn(x) x.resize(unique(all(x))-x.begin())
#define lc 2*id
#define rc 2*id+1

typedef vector<int> vi;

const int L = 2e5+10, hc=2;
int n,q;
ll p[hc],mod[hc],pp[hc][L],pps[hc][L];
vector<vi> av;
map<char,int> MP;

vi merge(vi a,vi b){
    vi ans;
    for(int i=0;i<n;i++){
        ans.pb((6-a[i]-b[i])%3);
    }
    return ans;
}
struct Hash{
    int h[hc];

    Hash(){
        fill(h,h+hc,0);
    }

    void add(int x,int ind){
        for(int i=0;i<hc;i++){
            h[i] += (x*pp[i][ind])%mod[i];
            h[i] %= mod[i];
        }
    }

    void set(int l,int r,int c){
        for(int i=0;i<hc;i++){
            h[i] = ((pps[i][r] - (l==0 ? 0 : pps[i][l-1]) + mod[i])*c)%mod[i];
        }
    }

    bool operator ==(Hash b){
        bool ok = 1;
        for(int i=0;i<hc;i++){
            ok = ok and (h[i] == b.h[i]);
        }
        return ok;
    }
};
Hash operator +(Hash a, Hash b){
    Hash ans;
    for(int i=0;i<hc;i++){
        ans.h[i] = (a.h[i] + b.h[i])%mod[i];
    }
    return ans;
}
vector<Hash> check; 

struct sagi{
    struct node{
        Hash h;
        int lazy;
    }t[L<<2];

    void build(int id,int l,int r){
        t[id].lazy = -1;
        if(l+1 == r){
            t[id].h.add(0,l);
            return;
        }
        int mid = (l+r)>>1;
        build(lc,l,mid);
        build(rc,mid,r);
        t[id].h = t[lc].h + t[rc].h;
    }

    void spread(int id,int l,int r){
        if(t[id].lazy == -1)
            return;
        if(rc < L*4){
            t[lc].lazy = t[rc].lazy = t[id].lazy;
        }
        t[id].h.set(l,r-1,t[id].lazy);
        t[id].lazy = -1;
    }

    void update(int id,int l,int r,int l2,int r2,int x){
        spread(id,l,r);
        if(l==l2 and r==r2){
            t[id].lazy = x;
            return;
        }
        int mid = (l+r)>>1;
        if(l2 < mid)
            update(lc,l,mid,l2,min(r2,mid),x);
        if(r2 > mid)
            update(rc,mid,r,max(l2,mid),r2,x);
        spread(lc,l,mid);
        spread(rc,mid,r);
        t[id].h = t[lc].h + t[rc].h;
    }

    Hash get(){
        spread(1,0,n);
        return t[1].h;
    }
}seg;

bool ok(Hash H){
    bool ans = 0;
    for(auto i:check){
        ans = ans or (i == H);
    }
    return ans;
}

int main(){

    MP['J'] = 0;
    MP['O'] = 1;
    MP['I'] = 2;

    p[0] = 7;
    p[1] = 11;
    mod[0] = 1e9+7;
    mod[1] = 1e9+9;

    for(int c=0;c<hc;c++){
        pp[c][0] = 1;
        pps[c][0] = 1;
        for(int i=1;i<L;i++){
            pp[c][i] = (pp[c][i-1]*p[c])%mod[c];
            pps[c][i] = (pps[c][i-1]+pp[c][i])%mod[c];
        }
    }

    cin>>n;
    for(int c=0;c<3;c++){
        vi tmp;
        for(int i=0;i<n;i++){
            char inp;
            cin>>inp;
            tmp.pb(MP[inp]);
        }
        av.pb(tmp);
    }

    av.pb(merge(av[0],av[1]));
    av.pb(merge(av[1],av[2]));
    av.pb(merge(av[0],av[2]));
    av.pb(merge(merge(av[0],av[1]),av[2]));
    av.pb(merge(merge(av[0],av[2]),av[1]));
    av.pb(merge(merge(av[1],av[2]),av[0]));

    sort(all(av));
    unicorn(av);

    for(auto v:av){
        Hash H;
        for(int i=0;i<n;i++){
            H.add(v[i],i);
        }
        check.pb(H);
    }

    cin>>q;
    for(int i=0;i<n;i++){
        char inp;
        cin>>inp;
        seg.update(1,0,n,i,i+1,MP[inp]);
    }

    cout<<(ok(seg.get()) ? "Yes" : "No")<<endl;
    for(int i=1;i<=q;i++){
        int l,r;
        char c;
        cin>>l>>r>>c; 
        l--;
        r--;
        seg.update(1,0,n,l,r+1,MP[c]); 
        cout<<(ok(seg.get()) ? "Yes" : "No")<<endl;
    }
}

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