제출 #704697

#제출 시각아이디문제언어결과실행 시간메모리
704697safaricolaCrossing (JOI21_crossing)C++17
0 / 100
498 ms2464 KiB
#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"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...