Submission #1257988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257988		ender_shayan	Crossing (JOI21_crossing)	C++20	100 / 100	3967 ms	28024 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F               first
#define S               second
#define pb              push_back
#define all(x)          x.begin(),x.end()
#define Mp              make_pair
#define endl            '\n'
#define for1(n)         for(int i=1;i<=n;i++)
#define for0(n)         for(int i=0;i<n;i++)
const ll mod=1e9+7;
const int N=1<<18,L=21;

int A[N],B[N],C[N],D[N],m,k,n,q,dp[N],pre[N];
vector<int>g[N];
bool seg[N*2][3][3][3];
int ans[N*2],lz[N*2];
int gt(char a){
    return (a=='J' ? 0:(a=='O' ? 1:2));
}
void doo(int v,int t){
    int anss=511;
    for(int x=0;x<3;x++)for(int y=0;y<3;y++)for(int z=0;z<3;z++)if(seg[v][x][y][z]){
        if(x!=t)
            anss&=(511^1);
        if(y!=t)
            anss&=(511^2);
        if(z!=t)
            anss&=(511^4);
        if((6-x-y)%3!=t)
            anss&=(511^8);
        if((6-y-z)%3!=t)
            anss&=(511^16);
        if((6-x-z)%3!=t)
            anss&=(511^32);
        if((3+x+y-z)%3!=t)
            anss&=(511^64);
        if((3+x-y+z)%3!=t)
            anss&=(511^128);
        if((3-x+y+z)%3!=t)
            anss&=(511^256);
    }
    ans[v]=anss;
}
void shift(int l,int r,int v){
    if(r-l==1 || lz[v]==-1)return;
    doo(v<<1,lz[v]);
    doo(v<<1|1,lz[v]);
    lz[v<<1]=lz[v<<1|1]=lz[v];
    lz[v]=-1;
}
void build(int l=1,int r=n+1,int v=1){
    lz[v]=-1;
    if(r-l==1){
        seg[v][A[l]][B[l]][C[l]]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,v<<1);
    build(mid,r,v<<1|1);
    for(int x=0;x<3;x++)for(int y=0;y<3;y++)for(int z=0;z<3;z++)seg[v][x][y][z]=seg[v<<1][x][y][z]|seg[v<<1|1][x][y][z];
}
void upd(int lx,int rx,int x,int l=1,int r=n+1,int v=1){
    shift(l,r,v);
    if(lx>=r || rx<=l)return;
    if(lx<=l && r<=rx){
        doo(v,x);
        lz[v]=x;
        return;
    }
    int mid=(l+r)>>1;
    upd(lx,rx,x,l,mid,v<<1);
    upd(lx,rx,x,mid,r,v<<1|1);
    ans[v]=ans[v<<1]&ans[v<<1|1];
}
int main(){
    fast_io
    cin>>n;
    string s;cin>>s;
    for1(n)A[i]=gt(s[i-1]);
    cin>>s;for1(n)B[i]=gt(s[i-1]);
    cin>>s;for1(n)C[i]=gt(s[i-1]);
    build();
    cin>>m;
    cin>>s;
    for1(n)upd(i,i+1,gt(s[i-1]));
    cout<<(ans[1] ? "Yes\n":"No\n");
    while(m--){
        int l,r;char a;cin>>l>>r>>a;
        upd(l,r+1,gt(a));
        cout<<(ans[1] ? "Yes\n":"No\n");
    }
}

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