Submission #1348666

#TimeUsernameProblemLanguageResultExecution timeMemory
1348666NewtonabcCrossing (JOI21_crossing)C++20
26 / 100
477 ms9288 KiB
#include<bits/stdc++.h>
using namespace std;
struct UWU{
    vector<int> s,lz;
    void init(int n){
        s.resize(4*n+2,0);
        lz.resize(4*n+2,-1);
    }
    void pushlz(int l,int r,int idx){
        if(lz[idx]==-1) return;
        s[idx]=lz[idx]*(r-l+1);
        if(l!=r) lz[idx*2]=lz[idx],lz[idx*2+1]=lz[idx];
        lz[idx]=-1;
    }
    void update(int l,int r,int idx,int a,int b,int val){
        pushlz(l,r,idx);
        if(a>r || b<l) return;
        if(a<=l && b>=r){
            lz[idx]=val;
            pushlz(l,r,idx);
            return;
        }
        int m=(l+r)/2;
        update(l,m,idx*2,a,b,val);
        update(m+1,r,idx*2+1,a,b,val);
        s[idx]=s[idx*2]+s[idx*2+1];
    }
    int query(int l,int r,int idx,int a,int b){
        pushlz(l,r,idx);
        if(a>r || b<l) return 0;
        if(a<=l && b>=r) return s[idx];
        int m=(l+r)/2;
        return query(l,m,idx*2,a,b)+query(m+1,r,idx*2+1,a,b);
    }
    int cnt(int sz){return query(0,sz,1,0,sz);}
}tj,to,ti;
vector<int> cj,co,ci;
void updj(int l,int r,int val){
    int il=lower_bound(cj.begin(),cj.end(),l)-cj.begin();
    int ir=upper_bound(cj.begin(),cj.end(),r)-cj.begin()-1;
    if(il>ir || il==cj.size()) return;
    tj.update(0,cj.size(),1,il,ir,val);
}
void updo(int l,int r,int val){
    int il=lower_bound(co.begin(),co.end(),l)-co.begin();
    int ir=upper_bound(co.begin(),co.end(),r)-co.begin()-1;
    if(il>ir || il==co.size()) return;
    to.update(0,co.size(),1,il,ir,val);
}
void updi(int l,int r,int val){
    int il=lower_bound(ci.begin(),ci.end(),l)-ci.begin();
    int ir=upper_bound(ci.begin(),ci.end(),r)-ci.begin()-1;
    if(il>ir || il==ci.size()) return;
    ti.update(0,ci.size(),1,il,ir,val);
}
int main(){
    int n; cin>>n;
    string sa,sb,sc; cin>>sa >>sb >>sc;
    for(int i=0;i<n;i++){
        if(sa[i]=='J') cj.push_back(i);
        else if(sa[i]=='O') co.push_back(i);
        else ci.push_back(i);
    }
    tj.init(cj.size()),to.init(co.size()),ti.init(ci.size());
    int q; cin>>q;
    string s; cin>>s;
    for(int i=0;i<n;i++){
        if(s[i]==sa[i]){
            if(s[i]=='J') updj(i,i,1),updo(i,i,0),updi(i,i,0);
            else if(s[i]=='O') updj(i,i,0),updo(i,i,1),updi(i,i,0);
            else updj(i,i,0),updo(i,i,0),updi(i,i,1);
        }
    }
    // for(int i=0;i<=cj.size();i++) cout<<tj.query(0,cj.size(),1,i,i) <<" ";
    // cout<<"\n";
    // for(int i=0;i<=co.size();i++) cout<<to.query(0,co.size(),1,i,i) <<" ";
    // cout<<"\n";
    // for(int i=0;i<=ci.size();i++) cout<<ti.query(0,ci.size(),1,i,i) <<" ";
    // cout<<"\n";
    if(tj.cnt(cj.size())+to.cnt(co.size())+ti.cnt(ci.size())==n) cout<<"Yes\n";
    else cout<<"No\n";
    for(int i=0;i<q;i++){
        char c;
        int l,r;
        cin>>l >>r >>c;
        l--,r--;
        if(c=='J') updj(l,r,1),updo(l,r,0),updi(l,r,0);
        else if(c=='O') updj(l,r,0),updo(l,r,1),updi(l,r,0);
        else updj(l,r,0),updo(l,r,0),updi(l,r,1);
        if(tj.cnt(cj.size())+to.cnt(co.size())+ti.cnt(ci.size())==n) cout<<"Yes\n";
        else cout<<"No\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...