제출 #1348712

#제출 시각아이디문제언어결과실행 시간메모리
1348712NewtonabcCrossing (JOI21_crossing)C++20
100 / 100
2752 ms23112 KiB
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
struct UWU{
    vector<int> s,lz;
    void init(int n){
        s.resize(4*n+2,0);
        lz.resize(4*n+2,-1);
        build(0,n,1);
    }
    void build(int l,int r,int idx){
        s[idx]=0,lz[idx]=-1;
        if(l==r) return;
        int m=(l+r)/2;
        build(l,m,idx*2);
        build(m+1,r,idx*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;
int ret[N];
vector<int> cj,co,ci;
vector<tuple<int,int,char>> qv;
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 n,q;
string s;
void cal(string sa){
    cj.clear(),co.clear(),ci.clear();
    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());
    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);
        }
    }
    if(tj.cnt(cj.size())+to.cnt(co.size())+ti.cnt(ci.size())==n) ret[0]=1;
    for(int i=1;i<=q;i++){
        auto [l,r,c]=qv[i-1];
        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) ret[i]=1;
    }
}
char f(char a,char b){
    if(a==b) return a;
    if(a=='J' && b=='O') return 'I';
    if(a=='J' && b=='I') return 'O';
    if(a=='O' && b=='J') return 'I';
    if(a=='O' && b=='I') return 'J';
    if(a=='I' && b=='J') return 'O';
    if(a=='I' && b=='O') return 'J';
    return 0;
}
string op(string a,string b){
    string ret;
    for(int i=0;i<n;i++) ret.push_back(f(a[i],b[i]));
    return ret;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    string sa,sb,sc; cin>>sa >>sb >>sc;
    cin>>q;
    cin>>s;
    set<string> cands;
    cands.insert(sa),cands.insert(sb),cands.insert(sc);
    cands.insert(op(sa,sb)),cands.insert(op(sb,sc)),cands.insert(op(sa,sc));
    cands.insert(op(sa,op(sb,sc))),cands.insert(op(sb,op(sa,sc))),cands.insert(op(sc,op(sa,sb)));
    for(int i=0;i<q;i++){
        int l,r;
        char c; cin>>l >>r >>c;
        l--,r--;
        qv.push_back({l,r,c});
    }
    for(auto cd:cands){
        cal(cd);
    }
    for(int i=0;i<=q;i++){
        if(ret[i]) 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...