Submission #704697

#	Time	Username	Problem	Language	Result	Execution time	Memory
704697		safaricola	Crossing (JOI21_crossing)	C++17	0 / 100	498 ms	2464 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep(i,n) for(ll i = 0; i < n; i++)
#define f first
#define s second
typedef pair<ll ,ll> ii;
string s[4];
char ch;
int n, a[10][200010],pre[10][4][200010],q,t,x,y;
int f(int x, int y){
    return (6-x-y)%3;
}
struct node{
    int s,e,m,v,lazy,id;
    node *l, *r;
    node(int S,int E,int ID){
        s=S,e=E,m=(s+e)/2;
        id=ID;v=0;lazy=-1;
        if(s==e)return;
        l= new node(s,m,id);
        r= new node(m+1,e,id);
    }
    void prop(){
        if(lazy==-1)return;
        v=pre[id][lazy][e]- (s==0 ? 0: pre[id][lazy][s-1]);
        if(s!=e){
            l->lazy=lazy;
            r->lazy=lazy;
        }
        lazy=-1;
    }
    void upd(int S,int E,int V){
        if(s==S&&e==E)lazy=V;
        else{
            prop();
            if(E<=m)l->upd(S,E,V);
            else if(S>m)r->upd(S,E,V);
            else{
                l->upd(S,m,V);
                r->upd(m+1,E,V);
            }
            l->prop();r->prop();
            v=l->v+r->v;
        }
    }
    int sum(int S,int E){
        prop();
        if(s==S&&e==E)return v;
        if(E<=m)return l->sum(S,E);
        else if(S>m)return r->sum(S,E);
        else return l->sum(S,m)+r->sum(m+1,E);
    }

}*root[10];
int main(){
    cin>>n>>s[0]>>s[1]>>s[2]>>q>>s[3];
    rep(i,3)rep(j,n){
        if(s[i][j]=='J')a[i][j]=0;
        else if(s[i][j]=='O')a[i][j]=1;
        else a[i][j]=2;
    }
    rep(i,n)a[3][i]=f(a[0][i],a[1][i]);
    rep(i,n)a[4][i]=f(a[2][i],a[1][i]);
    rep(i,n)a[5][i]=f(a[0][i],a[2][i]);
    rep(i,n)a[6][i]=f(a[3][i],a[4][i]);
    rep(i,n)a[7][i]=f(a[5][i],a[4][i]);
    rep(i,n)a[8][i]=f(a[3][i],a[5][i]);
    //rep(i,9){rep(j,n)cout<<a[i][j];cout<<endl;}
    rep(i,9)rep(j,3)rep(k,n){
        pre[i][j][k]=(k==0 ? 0: pre[i][j][k-1])+(j==a[i][k]);
    }
    //rep(i,9)rep(j,3){cout<<i<<j<<": ";rep(k,n)cout<<pre[i][j][k];cout<<endl;}
    
    rep(i,9)root[i] = new node(0,n,i);
    rep(i,9)rep(j,n){
        if(s[3][j]=='J')t=0;
        else if(s[3][j]=='O')t=1;
        else t=2;
        root[i]->upd(j,j,t);
    }
    bool flag=true;
    rep(i,9)if(root[i]-> sum(0,n)==n){
        flag=false;
        cout<<"YES\n";
        break;
    }
    if(flag)cout<<"NO\n";
    while(q--){
        cin>>x>>y>>ch;x--;y--;
        if(ch=='J')t=0;
        else if(ch=='O')t=1;
        else t=2;
        rep(i,9){
            root[i]-> upd(x,y,t);
        }
        bool flag=true;
        rep(i,9)if(root[i]->sum(0,n)==n){
            flag=false;
            cout<<"YES\n";
            break;
        }
        if(flag)cout<<"NO\n";
    }

}

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