Submission #1304887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304887		the_ZHER	Crossing (JOI21_crossing)	C++20	26 / 100	140 ms	11456 KiB

Main

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

#define int long long
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N=2e5+10;
const int inf=1e18;
const int mod=1e9+7;
struct edge{
    int x,y,w;
};
int t[4*N];
char add[4*N];
int pr[N];
int pr1[N];
int pr2[N];
string res,s,s1,s2;
void build(int n,int tl,int tr){
    if(tl==tr){
        if(res[tl-1]==s[tl-1]){
            t[n]=1;
        }
        return;
    }
    int mid=(tl+tr)/2;
    build(n*2,tl,mid);
    build(n*2+1,mid+1,tr);
    t[n]=t[n*2]+t[n*2+1];
}
void push(int n,int tl,int tr){
    if(add[n]=='J'||add[n]=='O'||add[n]=='I'){
        int cnt=0;
        if(add[n]=='J'){
            if(tl==1){
                cnt=pr[tr-1];
            }else{
                cnt=pr[tr-1]-pr[tl-2];
            }
        }
        if(add[n]=='O'){
            if(tl==1){
                cnt=pr1[tr-1];
            }else{
                cnt=pr1[tr-1]-pr1[tl-2];
            }
        }
        if(add[n]=='I'){
            if(tl==1){
                cnt=pr2[tr-1];
            }else{
                cnt=pr2[tr-1]-pr2[tl-2];
            }
        }
        t[n]=cnt;
        if(tl!=tr){
            add[n*2]=add[n];
            add[n*2+1]=add[n];
        }
        add[n]=' ';
   }
}
void upd(int n,int tl,int tr,int l,int r,char x){
    push(n,tl,tr);
    if(tr<l||r<tl){
        return;
    }
    if(l<=tl&&tr<=r){
        add[n]=x;
        push(n,tl,tr);
        return;
    }
    int mid=(tl+tr)/2;
    upd(n*2,tl,mid,l,r,x);
    upd(n*2+1,mid+1,tr,l,r,x);
    t[n]=t[n*2]+t[n*2+1];
}
signed main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(nullptr);
    int n;
    cin>>n;
    cin>>s>>s1>>s2;
    int q;
    cin>>q;
    cin>>res;
    for(int i=0;i<s.size();i++){
        if(s[i]=='J'){
            pr[i]=1;
        }
        if(s[i]=='O'){
            pr1[i]=1;
        }
        if(s[i]=='I'){
            pr2[i]=1;
        }
        pr[i]+=pr[i-1];
        pr1[i]+=pr1[i-1];
        pr2[i]+=pr2[i-1];
    }
    build(1,1,n);
    if(t[1]==n){
        cout<<"Yes\n";
    }else{
        cout<<"No\n";
    }
    for(int i=1;i<=q;i++){
        int l,r;
        char c;
        cin>>l>>r>>c;
        upd(1,1,n,l,r,c);
        if(t[1]==n){
            cout<<"Yes\n";
        }else{
            cout<<"No\n";
        }
    }
}

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