// I may fail a thousand times
// But there is no giving up
// IOI - here I come
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int BASE=3;
const int MOD1=(int)1e9+9;
const int MOD2=(int)1e9+6;
string s;
map<char,int> mp;
int lazy[(int)8e5+5];
int tree[(int)8e5+5][2];
int pref[(int)2e5+5][2];
string calc(string x,string y){
string ret="";
int sz=(int)x.length();
for(int i=0;i<sz;i++){
if(x[i]==y[i])ret+=x[i];
else{
char a=x[i];
char b=y[i];
if(a>b)swap(a,b);
if(a=='I'&&b=='J')ret+='O';
if(a=='I'&&b=='O')ret+='J';
if(a=='J'&&b=='O')ret+='I';
}
}
return ret;
}
int mul(int a,int b,int MOD){
int ret=(a*b)%MOD;
if(ret<0)ret+=MOD;
return ret;
}
int add(int a,int b,int MOD){
int ret=(a+b)%MOD;
if(ret<0)ret+=MOD;
return ret;
}
void build(int v,int l,int r){
if(l==r){
tree[v][0]=mul(mp[s[l-1]],add(pref[r][0],-pref[l-1][0],MOD1),MOD1);
tree[v][1]=mul(mp[s[l-1]],add(pref[r][1],-pref[l-1][1],MOD2),MOD2);
return;
}
int m=(l+r)/2;
build(2*v,l,m);
build(2*v+1,m+1,r);
tree[v][0]=add(tree[2*v][0],tree[2*v+1][0],MOD1);
tree[v][1]=add(tree[2*v][1],tree[2*v+1][1],MOD2);
}
void push(int v,int l,int r){
if(l>r)return;
if(lazy[v]!=-1){
if(l!=r){
lazy[2*v]=lazy[v];
lazy[2*v+1]=lazy[v];
}
tree[v][0]=mul(lazy[v],add(pref[r][0],-pref[l-1][0],MOD1),MOD1);
tree[v][1]=mul(lazy[v],add(pref[r][1],-pref[l-1][1],MOD2),MOD2);
lazy[v]=-1;
}
}
void upd(int v,int l,int r,int ul,int ur,int t){
push(v,l,r);
if(l>r||ul>ur||l>ur||r<ul)return;
if(l>=ul&&r<=ur){
lazy[v]=t;
push(v,l,r);
return;
}
int m=(l+r)/2;
upd(2*v,l,m,ul,ur,t);
upd(2*v+1,m+1,r,ul,ur,t);
tree[v][0]=add(tree[2*v][0],tree[2*v+1][0],MOD1);
tree[v][1]=add(tree[2*v][1],tree[2*v+1][1],MOD2);
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n;cin>>n;
mp['I']=0;
mp['J']=1;
mp['O']=2;
vector<string> v(3);
for(int i=0;i<3;i++)cin>>v[i];
queue<string> q;
for(int i=0;i<3;i++)q.push(v[i]);
v.clear();
map<string,int> vis;
for(;!q.empty();){
string x=q.front();q.pop();
if(vis[x])continue;
vis[x]=1;
v.push_back(x);
for(auto y:v){
string z=calc(x,y);
q.push(z);
}
}
int curbase1=1,curbase2=1;
for(int i=1;i<=n;i++){
pref[i][0]=add(pref[i-1][0],curbase1,MOD1);
pref[i][1]=add(pref[i-1][1],curbase2,MOD2);
curbase1=mul(curbase1,BASE,MOD1);
curbase2=mul(curbase2,BASE,MOD2);
}
vector<int> res0,res1;
for(string s:v){
int cur0,cur1;cur0=cur1=0;
for(int i=0;i<(int)s.length();i++){
cur0=add(cur0,mul(mp[s[i]],add(pref[i+1][0],-pref[i][0],MOD1),MOD1),MOD1);
cur1=add(cur1,mul(mp[s[i]],add(pref[i+1][1],-pref[i][1],MOD2),MOD2),MOD2);
}
res0.push_back(cur0);
res1.push_back(cur1);
}
int t;cin>>t;
cin>>s;
build(1,1,n);
int flag=0;
for(int i=0;i<(int)res0.size();i++){
if(tree[1][0]==res0[i]&&tree[1][1]==res1[i]){
flag=1;
}
}
flag?cout<<"Yes\n":cout<<"No\n";
for(;t;t--){
int l,r;cin>>l>>r;
char c;cin>>c;
int x=mp[c];
upd(1,1,n,l,r,x);
int flag=0;
for(int i=0;i<(int)res0.size();i++){
if(tree[1][0]==res0[i]&&tree[1][1]==res1[i]){
flag=1;
}
}
flag?cout<<"Yes\n":cout<<"No\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
2244 KB |
Output is correct |
2 |
Correct |
85 ms |
2324 KB |
Output is correct |
3 |
Correct |
89 ms |
2320 KB |
Output is correct |
4 |
Correct |
76 ms |
2356 KB |
Output is correct |
5 |
Correct |
71 ms |
2276 KB |
Output is correct |
6 |
Correct |
71 ms |
2284 KB |
Output is correct |
7 |
Correct |
69 ms |
2368 KB |
Output is correct |
8 |
Correct |
73 ms |
2296 KB |
Output is correct |
9 |
Correct |
74 ms |
2352 KB |
Output is correct |
10 |
Correct |
72 ms |
2324 KB |
Output is correct |
11 |
Correct |
81 ms |
2360 KB |
Output is correct |
12 |
Correct |
72 ms |
2340 KB |
Output is correct |
13 |
Correct |
79 ms |
2372 KB |
Output is correct |
14 |
Correct |
73 ms |
2336 KB |
Output is correct |
15 |
Correct |
73 ms |
2320 KB |
Output is correct |
16 |
Correct |
72 ms |
2396 KB |
Output is correct |
17 |
Correct |
76 ms |
2380 KB |
Output is correct |
18 |
Correct |
82 ms |
2336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
2244 KB |
Output is correct |
2 |
Correct |
85 ms |
2324 KB |
Output is correct |
3 |
Correct |
89 ms |
2320 KB |
Output is correct |
4 |
Correct |
76 ms |
2356 KB |
Output is correct |
5 |
Correct |
71 ms |
2276 KB |
Output is correct |
6 |
Correct |
71 ms |
2284 KB |
Output is correct |
7 |
Correct |
69 ms |
2368 KB |
Output is correct |
8 |
Correct |
73 ms |
2296 KB |
Output is correct |
9 |
Correct |
74 ms |
2352 KB |
Output is correct |
10 |
Correct |
72 ms |
2324 KB |
Output is correct |
11 |
Correct |
81 ms |
2360 KB |
Output is correct |
12 |
Correct |
72 ms |
2340 KB |
Output is correct |
13 |
Correct |
79 ms |
2372 KB |
Output is correct |
14 |
Correct |
73 ms |
2336 KB |
Output is correct |
15 |
Correct |
73 ms |
2320 KB |
Output is correct |
16 |
Correct |
72 ms |
2396 KB |
Output is correct |
17 |
Correct |
76 ms |
2380 KB |
Output is correct |
18 |
Correct |
82 ms |
2336 KB |
Output is correct |
19 |
Correct |
320 ms |
19100 KB |
Output is correct |
20 |
Correct |
311 ms |
15820 KB |
Output is correct |
21 |
Correct |
187 ms |
18784 KB |
Output is correct |
22 |
Correct |
184 ms |
18360 KB |
Output is correct |
23 |
Correct |
116 ms |
3444 KB |
Output is correct |
24 |
Correct |
113 ms |
3444 KB |
Output is correct |
25 |
Correct |
212 ms |
19256 KB |
Output is correct |
26 |
Correct |
213 ms |
19100 KB |
Output is correct |
27 |
Correct |
227 ms |
19060 KB |
Output is correct |
28 |
Correct |
261 ms |
19148 KB |
Output is correct |
29 |
Correct |
206 ms |
18996 KB |
Output is correct |
30 |
Correct |
125 ms |
3396 KB |
Output is correct |
31 |
Correct |
211 ms |
19124 KB |
Output is correct |
32 |
Correct |
229 ms |
18736 KB |
Output is correct |
33 |
Correct |
118 ms |
3408 KB |
Output is correct |
34 |
Correct |
253 ms |
19112 KB |
Output is correct |
35 |
Correct |
169 ms |
17948 KB |
Output is correct |
36 |
Correct |
113 ms |
3328 KB |
Output is correct |
37 |
Correct |
115 ms |
3356 KB |
Output is correct |
38 |
Correct |
250 ms |
15908 KB |
Output is correct |
39 |
Incorrect |
132 ms |
15016 KB |
Output isn't correct |
40 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
2244 KB |
Output is correct |
2 |
Correct |
85 ms |
2324 KB |
Output is correct |
3 |
Correct |
89 ms |
2320 KB |
Output is correct |
4 |
Correct |
76 ms |
2356 KB |
Output is correct |
5 |
Correct |
71 ms |
2276 KB |
Output is correct |
6 |
Correct |
71 ms |
2284 KB |
Output is correct |
7 |
Correct |
69 ms |
2368 KB |
Output is correct |
8 |
Correct |
73 ms |
2296 KB |
Output is correct |
9 |
Correct |
74 ms |
2352 KB |
Output is correct |
10 |
Correct |
72 ms |
2324 KB |
Output is correct |
11 |
Correct |
81 ms |
2360 KB |
Output is correct |
12 |
Correct |
72 ms |
2340 KB |
Output is correct |
13 |
Correct |
79 ms |
2372 KB |
Output is correct |
14 |
Correct |
73 ms |
2336 KB |
Output is correct |
15 |
Correct |
73 ms |
2320 KB |
Output is correct |
16 |
Correct |
72 ms |
2396 KB |
Output is correct |
17 |
Correct |
76 ms |
2380 KB |
Output is correct |
18 |
Correct |
82 ms |
2336 KB |
Output is correct |
19 |
Correct |
81 ms |
2372 KB |
Output is correct |
20 |
Correct |
90 ms |
2212 KB |
Output is correct |
21 |
Correct |
75 ms |
2324 KB |
Output is correct |
22 |
Correct |
63 ms |
2200 KB |
Output is correct |
23 |
Correct |
83 ms |
2308 KB |
Output is correct |
24 |
Correct |
69 ms |
2244 KB |
Output is correct |
25 |
Correct |
73 ms |
2408 KB |
Output is correct |
26 |
Correct |
67 ms |
2296 KB |
Output is correct |
27 |
Correct |
74 ms |
2476 KB |
Output is correct |
28 |
Correct |
68 ms |
2192 KB |
Output is correct |
29 |
Correct |
78 ms |
2400 KB |
Output is correct |
30 |
Correct |
65 ms |
2288 KB |
Output is correct |
31 |
Correct |
74 ms |
2408 KB |
Output is correct |
32 |
Correct |
78 ms |
2480 KB |
Output is correct |
33 |
Correct |
77 ms |
2364 KB |
Output is correct |
34 |
Correct |
67 ms |
2240 KB |
Output is correct |
35 |
Correct |
78 ms |
2508 KB |
Output is correct |
36 |
Correct |
77 ms |
2356 KB |
Output is correct |
37 |
Correct |
79 ms |
2416 KB |
Output is correct |
38 |
Correct |
76 ms |
2384 KB |
Output is correct |
39 |
Correct |
72 ms |
2308 KB |
Output is correct |
40 |
Correct |
77 ms |
2388 KB |
Output is correct |
41 |
Correct |
73 ms |
2336 KB |
Output is correct |
42 |
Correct |
75 ms |
2372 KB |
Output is correct |
43 |
Correct |
71 ms |
2372 KB |
Output is correct |
44 |
Correct |
76 ms |
2404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
2244 KB |
Output is correct |
2 |
Correct |
85 ms |
2324 KB |
Output is correct |
3 |
Correct |
89 ms |
2320 KB |
Output is correct |
4 |
Correct |
76 ms |
2356 KB |
Output is correct |
5 |
Correct |
71 ms |
2276 KB |
Output is correct |
6 |
Correct |
71 ms |
2284 KB |
Output is correct |
7 |
Correct |
69 ms |
2368 KB |
Output is correct |
8 |
Correct |
73 ms |
2296 KB |
Output is correct |
9 |
Correct |
74 ms |
2352 KB |
Output is correct |
10 |
Correct |
72 ms |
2324 KB |
Output is correct |
11 |
Correct |
81 ms |
2360 KB |
Output is correct |
12 |
Correct |
72 ms |
2340 KB |
Output is correct |
13 |
Correct |
79 ms |
2372 KB |
Output is correct |
14 |
Correct |
73 ms |
2336 KB |
Output is correct |
15 |
Correct |
73 ms |
2320 KB |
Output is correct |
16 |
Correct |
72 ms |
2396 KB |
Output is correct |
17 |
Correct |
76 ms |
2380 KB |
Output is correct |
18 |
Correct |
82 ms |
2336 KB |
Output is correct |
19 |
Correct |
320 ms |
19100 KB |
Output is correct |
20 |
Correct |
311 ms |
15820 KB |
Output is correct |
21 |
Correct |
187 ms |
18784 KB |
Output is correct |
22 |
Correct |
184 ms |
18360 KB |
Output is correct |
23 |
Correct |
116 ms |
3444 KB |
Output is correct |
24 |
Correct |
113 ms |
3444 KB |
Output is correct |
25 |
Correct |
212 ms |
19256 KB |
Output is correct |
26 |
Correct |
213 ms |
19100 KB |
Output is correct |
27 |
Correct |
227 ms |
19060 KB |
Output is correct |
28 |
Correct |
261 ms |
19148 KB |
Output is correct |
29 |
Correct |
206 ms |
18996 KB |
Output is correct |
30 |
Correct |
125 ms |
3396 KB |
Output is correct |
31 |
Correct |
211 ms |
19124 KB |
Output is correct |
32 |
Correct |
229 ms |
18736 KB |
Output is correct |
33 |
Correct |
118 ms |
3408 KB |
Output is correct |
34 |
Correct |
253 ms |
19112 KB |
Output is correct |
35 |
Correct |
169 ms |
17948 KB |
Output is correct |
36 |
Correct |
113 ms |
3328 KB |
Output is correct |
37 |
Correct |
115 ms |
3356 KB |
Output is correct |
38 |
Correct |
250 ms |
15908 KB |
Output is correct |
39 |
Incorrect |
132 ms |
15016 KB |
Output isn't correct |
40 |
Halted |
0 ms |
0 KB |
- |