Submission #1143625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143625		owoovo	Crossing (JOI21_crossing)	C++20	100 / 100	375 ms	28780 KiB

Main

#include<bits/stdc++.h>
#define ll long long 
#define F first 
#define S second 
using namespace std;
int val[9][200010];
bool all[3][9][800010],can[9][800010];
int tag[800010];
void build(int l,int r,int id){// l,r 1-base
    tag[id]=-1;
    if(l==r){
        for(int i=0;i<9;i++){
            all[val[i][l]][i][id]=1;
        }
        return;
    }
    int m=(l+r)>>1;
    build(l,m,id*2+1);
    build(m+1,r,id*2+2);
    for(int i=0;i<3;i++){
        for(int j=0;j<9;j++){
            all[i][j][id]=all[i][j][id*2+1]&all[i][j][id*2+2];
        }
    }
    return;
}
void addtag(int id,int v){
    tag[id]=v;
    for(int i=0;i<9;i++){
        can[i][id]=all[v][i][id];
    }
}
void pull(int id){
    for(int i=0;i<9;i++){
        can[i][id]=can[i][id*2+1]&can[i][id*2+2];
    }
}
void push(int id){
    if(tag[id]!=-1){
        addtag(id*2+1,tag[id]);
        addtag(id*2+2,tag[id]);
        tag[id]=-1;
    }
}
void modify(int l,int r,int id,int L,int R,int v){
    if(l==L&&r==R){
        addtag(id,v);
        return;
    }
    push(id);
    int m=(l+r)>>1;
    if(R<=m)modify(l,m,id*2+1,L,R,v);
    else if(L>m)modify(m+1,r,id*2+2,L,R,v);
    else {
        modify(l,m,id*2+1,L,m,v);
        modify(m+1,r,id*2+2,m+1,R,v);
    }
    pull(id);
}
vector<vector<int>> mov={{0,1,3},{1,2,4},{0,2,5},{2,3,6},{1,5,7},{0,4,8}};
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    map<char,int> mp={{'J',0},{'O',1},{'I',2}};
    int n;
    cin>>n;
    for(int i=0;i<3;i++){
        for(int j=1;j<=n;j++){
            char c;
            cin>>c;
            val[i][j]=mp[c];
        }
    }
    for(auto v:mov){
        int a=v[0],b=v[1],c=v[2];
        for(int j=1;j<=n;j++){
            val[c][j]=(2*val[a][j]+2*val[b][j])%3;
        }
    }
    build(1,n,0);
    auto query=[&]{
        bool ok=0;
        for(int i=0;i<9;i++)ok|=can[i][0];
        if(ok)cout<<"Yes\n";
        else cout<<"No\n";
    };
    int q;
    cin>>q;
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        modify(1,n,0,i,i,mp[c]);
    }
    query();
    for(int i=1;i<=q;i++){
        int l,r;
        char c;
        cin>>l>>r>>c;
        modify(1,n,0,l,r,mp[c]);
        query();
    }


    return 0;
}

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