This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
//#define int long long
#define pii pair<int,int>
#define ret return
#define fr first
#define sc second
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define nosol puts("-1");
#define pb push_back
#define endi puts("");
#define ordered_set tree <int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int N = 2e5+12,INF = 1e9+7;
int q[10][N],w[N],n,pref[N][10][4];
string s[5];
struct derevo{
int lp,can;
derevo (int x=0): can(x),lp(-1) {};
} der[4*N][10];
void fun(int a,int b,int c){
for (int i=1;i<=n;++i)
q[c][i] = ((3-(q[a][i]+q[b][i])+3)%3);
}
void build(int v,int l,int r,int j){
if (l == r){
der[v][j].can = (q[j][l] == w[l]);
ret ;
}
int m = l+r>>1;
build(v<<1,l,m,j);
build(v<<1|1,m+1,r,j);
der[v][j].can = (der[v<<1][j].can && der[v<<1|1][j].can);
}
void push(int v,int j,int l,int r){
if (der[v][j].lp == -1)ret ;
if (r == l){
der[v][j].can = (der[v][j].lp == q[j][l]);
der[v][j].lp = -1;
ret ;
}
int m = l+r>>1;
der[v<<1][j].can = ((pref[m][j][der[v][j].lp]-pref[l-1][j][der[v][j].lp]) == (m-l+1));
der[v<<1|1][j].can = ((pref[r][j][der[v][j].lp]-pref[m][j][der[v][j].lp]) == (r-m));
der[v<<1][j].lp = der[v][j].lp;
der[v<<1|1][j].lp = der[v][j].lp;
der[v][j].can = (der[v<<1][j].can && der[v<<1|1][j].can);
der[v][j].lp = -1;
}
void update(int v,int l,int r,int ql,int qr,int x,int j){
push(v,j,l,r);
if (l > qr || r < ql){
ret ;
}
if (ql <= l && r <= qr){
der[v][j].lp = x;
der[v][j].can = ((pref[r][j][x] - pref[l-1][j][x]) == (r-l+1));
push(v,j,l,r);
ret ;
}
int m = l+r>>1;
update(v<<1,l,m,ql,qr,x,j);
update(v<<1|1,m+1,r,ql,qr,x,j);
der[v][j].can = (der[v<<1][j].can && der[v<<1|1][j].can);
}
void is(){
for (int j=0;j<9;++j){
if (der[1][j].can){
cout <<"Yes\n";ret ;
}
}
cout <<"No\n";
}
int main(){
int i,m,j;
cin>>n;
cin>>s[0]>>s[1]>>s[2];
for (i=0;i<n;++i){
if (s[0][i] == 'J')
q[0][i+1] = 1;
if (s[1][i] == 'J')
q[1][i+1] = 1;
if (s[2][i] == 'J')
q[2][i+1] = 1;
if (s[0][i] == 'O')
q[0][i+1] = 2;
if (s[1][i] == 'O')
q[1][i+1] = 2;
if (s[2][i] == 'O')
q[2][i+1] = 2;
}
fun(0,1,3);
fun(0,2,4);
fun(1,2,5);
fun(3,2,6);
fun(4,1,7);
fun(5,0,8);
cin>>m;
cin>>s[3];
for (j=0;j<9;++j){
for (i=1;i<=n;++i){
pref[i][j][0] = pref[i-1][j][0];
pref[i][j][1] = pref[i-1][j][1];
pref[i][j][2] = pref[i-1][j][2];
pref[i][j][q[j][i]]++;
}
}
for (i=0;i<n;++i){
if (s[3][i] == 'J')
w[i+1] = 1;
if (s[3][i] == 'O')
w[i+1] = 2;
}
for (j=0;j<9;++j)
build(1,1,n,j);
is();
while (m--){
int l,r,z=0;
char ch;
cin>>l>>r>>ch;
if (ch == 'J')z = 1;
if (ch == 'O')z = 2;
for (j=0;j<9;++j){
update(1,1,n,l,r,z,j);
}
is();
}
}
Compilation message (stderr)
Main.cpp: In constructor 'derevo::derevo(int)':
Main.cpp:24:9: warning: 'derevo::can' will be initialized after [-Wreorder]
24 | int lp,can;
| ^~~
Main.cpp:24:6: warning: 'int derevo::lp' [-Wreorder]
24 | int lp,can;
| ^~
Main.cpp:25:2: warning: when initialized here [-Wreorder]
25 | derevo (int x=0): can(x),lp(-1) {};
| ^~~~~~
Main.cpp: In function 'void build(int, int, int, int)':
Main.cpp:38:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int m = l+r>>1;
| ~^~
Main.cpp: In function 'void push(int, int, int, int)':
Main.cpp:51:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
51 | int m = l+r>>1;
| ~^~
Main.cpp: In function 'void update(int, int, int, int, int, int, int)':
Main.cpp:71:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | int m = l+r>>1;
| ~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |