// 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=101;
const int MOD1=(int)1e9+9;
const int MOD2=(int)1e9+7;
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);
map<string,int> vis;
for(int i=0;i<3;i++)cin>>v[i],vis[v[i]]=1;
for(int i=0;i<(int)v.size();i++){
for(int j=0;j<(int)v.size();j++){
string nxt=calc(v[i],v[j]);
if(vis[nxt])continue;
v.push_back(nxt);
vis[nxt]=1;
}
}
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 |
73 ms |
1088 KB |
Output is correct |
2 |
Correct |
83 ms |
1108 KB |
Output is correct |
3 |
Correct |
85 ms |
1192 KB |
Output is correct |
4 |
Correct |
68 ms |
1140 KB |
Output is correct |
5 |
Correct |
67 ms |
1076 KB |
Output is correct |
6 |
Correct |
71 ms |
1084 KB |
Output is correct |
7 |
Correct |
71 ms |
1172 KB |
Output is correct |
8 |
Correct |
71 ms |
1116 KB |
Output is correct |
9 |
Correct |
74 ms |
1264 KB |
Output is correct |
10 |
Correct |
80 ms |
1332 KB |
Output is correct |
11 |
Correct |
73 ms |
1224 KB |
Output is correct |
12 |
Correct |
71 ms |
1220 KB |
Output is correct |
13 |
Correct |
77 ms |
1096 KB |
Output is correct |
14 |
Correct |
72 ms |
1224 KB |
Output is correct |
15 |
Correct |
76 ms |
1348 KB |
Output is correct |
16 |
Correct |
72 ms |
1136 KB |
Output is correct |
17 |
Correct |
72 ms |
1224 KB |
Output is correct |
18 |
Correct |
80 ms |
1128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
1088 KB |
Output is correct |
2 |
Correct |
83 ms |
1108 KB |
Output is correct |
3 |
Correct |
85 ms |
1192 KB |
Output is correct |
4 |
Correct |
68 ms |
1140 KB |
Output is correct |
5 |
Correct |
67 ms |
1076 KB |
Output is correct |
6 |
Correct |
71 ms |
1084 KB |
Output is correct |
7 |
Correct |
71 ms |
1172 KB |
Output is correct |
8 |
Correct |
71 ms |
1116 KB |
Output is correct |
9 |
Correct |
74 ms |
1264 KB |
Output is correct |
10 |
Correct |
80 ms |
1332 KB |
Output is correct |
11 |
Correct |
73 ms |
1224 KB |
Output is correct |
12 |
Correct |
71 ms |
1220 KB |
Output is correct |
13 |
Correct |
77 ms |
1096 KB |
Output is correct |
14 |
Correct |
72 ms |
1224 KB |
Output is correct |
15 |
Correct |
76 ms |
1348 KB |
Output is correct |
16 |
Correct |
72 ms |
1136 KB |
Output is correct |
17 |
Correct |
72 ms |
1224 KB |
Output is correct |
18 |
Correct |
80 ms |
1128 KB |
Output is correct |
19 |
Correct |
347 ms |
18176 KB |
Output is correct |
20 |
Correct |
298 ms |
14804 KB |
Output is correct |
21 |
Correct |
209 ms |
18036 KB |
Output is correct |
22 |
Correct |
200 ms |
17384 KB |
Output is correct |
23 |
Correct |
133 ms |
2372 KB |
Output is correct |
24 |
Correct |
119 ms |
2468 KB |
Output is correct |
25 |
Correct |
210 ms |
18000 KB |
Output is correct |
26 |
Correct |
230 ms |
17984 KB |
Output is correct |
27 |
Correct |
248 ms |
18072 KB |
Output is correct |
28 |
Correct |
255 ms |
18024 KB |
Output is correct |
29 |
Correct |
239 ms |
17988 KB |
Output is correct |
30 |
Correct |
124 ms |
2500 KB |
Output is correct |
31 |
Correct |
224 ms |
18048 KB |
Output is correct |
32 |
Correct |
249 ms |
17648 KB |
Output is correct |
33 |
Correct |
116 ms |
2372 KB |
Output is correct |
34 |
Correct |
245 ms |
18008 KB |
Output is correct |
35 |
Correct |
189 ms |
17024 KB |
Output is correct |
36 |
Correct |
113 ms |
2372 KB |
Output is correct |
37 |
Correct |
112 ms |
2260 KB |
Output is correct |
38 |
Correct |
276 ms |
14840 KB |
Output is correct |
39 |
Incorrect |
154 ms |
14036 KB |
Output isn't correct |
40 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
1088 KB |
Output is correct |
2 |
Correct |
83 ms |
1108 KB |
Output is correct |
3 |
Correct |
85 ms |
1192 KB |
Output is correct |
4 |
Correct |
68 ms |
1140 KB |
Output is correct |
5 |
Correct |
67 ms |
1076 KB |
Output is correct |
6 |
Correct |
71 ms |
1084 KB |
Output is correct |
7 |
Correct |
71 ms |
1172 KB |
Output is correct |
8 |
Correct |
71 ms |
1116 KB |
Output is correct |
9 |
Correct |
74 ms |
1264 KB |
Output is correct |
10 |
Correct |
80 ms |
1332 KB |
Output is correct |
11 |
Correct |
73 ms |
1224 KB |
Output is correct |
12 |
Correct |
71 ms |
1220 KB |
Output is correct |
13 |
Correct |
77 ms |
1096 KB |
Output is correct |
14 |
Correct |
72 ms |
1224 KB |
Output is correct |
15 |
Correct |
76 ms |
1348 KB |
Output is correct |
16 |
Correct |
72 ms |
1136 KB |
Output is correct |
17 |
Correct |
72 ms |
1224 KB |
Output is correct |
18 |
Correct |
80 ms |
1128 KB |
Output is correct |
19 |
Correct |
81 ms |
1192 KB |
Output is correct |
20 |
Correct |
88 ms |
1104 KB |
Output is correct |
21 |
Correct |
75 ms |
1220 KB |
Output is correct |
22 |
Correct |
64 ms |
1092 KB |
Output is correct |
23 |
Correct |
71 ms |
1220 KB |
Output is correct |
24 |
Correct |
69 ms |
1132 KB |
Output is correct |
25 |
Correct |
75 ms |
1184 KB |
Output is correct |
26 |
Correct |
66 ms |
1092 KB |
Output is correct |
27 |
Correct |
72 ms |
1168 KB |
Output is correct |
28 |
Correct |
64 ms |
1060 KB |
Output is correct |
29 |
Correct |
72 ms |
1160 KB |
Output is correct |
30 |
Correct |
65 ms |
1092 KB |
Output is correct |
31 |
Correct |
72 ms |
1188 KB |
Output is correct |
32 |
Correct |
69 ms |
1132 KB |
Output is correct |
33 |
Correct |
79 ms |
1160 KB |
Output is correct |
34 |
Correct |
64 ms |
1132 KB |
Output is correct |
35 |
Correct |
72 ms |
1208 KB |
Output is correct |
36 |
Correct |
73 ms |
1192 KB |
Output is correct |
37 |
Correct |
73 ms |
1148 KB |
Output is correct |
38 |
Correct |
76 ms |
1124 KB |
Output is correct |
39 |
Correct |
73 ms |
1120 KB |
Output is correct |
40 |
Correct |
73 ms |
1132 KB |
Output is correct |
41 |
Correct |
72 ms |
1212 KB |
Output is correct |
42 |
Correct |
87 ms |
1356 KB |
Output is correct |
43 |
Correct |
71 ms |
1276 KB |
Output is correct |
44 |
Correct |
73 ms |
1220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
1088 KB |
Output is correct |
2 |
Correct |
83 ms |
1108 KB |
Output is correct |
3 |
Correct |
85 ms |
1192 KB |
Output is correct |
4 |
Correct |
68 ms |
1140 KB |
Output is correct |
5 |
Correct |
67 ms |
1076 KB |
Output is correct |
6 |
Correct |
71 ms |
1084 KB |
Output is correct |
7 |
Correct |
71 ms |
1172 KB |
Output is correct |
8 |
Correct |
71 ms |
1116 KB |
Output is correct |
9 |
Correct |
74 ms |
1264 KB |
Output is correct |
10 |
Correct |
80 ms |
1332 KB |
Output is correct |
11 |
Correct |
73 ms |
1224 KB |
Output is correct |
12 |
Correct |
71 ms |
1220 KB |
Output is correct |
13 |
Correct |
77 ms |
1096 KB |
Output is correct |
14 |
Correct |
72 ms |
1224 KB |
Output is correct |
15 |
Correct |
76 ms |
1348 KB |
Output is correct |
16 |
Correct |
72 ms |
1136 KB |
Output is correct |
17 |
Correct |
72 ms |
1224 KB |
Output is correct |
18 |
Correct |
80 ms |
1128 KB |
Output is correct |
19 |
Correct |
347 ms |
18176 KB |
Output is correct |
20 |
Correct |
298 ms |
14804 KB |
Output is correct |
21 |
Correct |
209 ms |
18036 KB |
Output is correct |
22 |
Correct |
200 ms |
17384 KB |
Output is correct |
23 |
Correct |
133 ms |
2372 KB |
Output is correct |
24 |
Correct |
119 ms |
2468 KB |
Output is correct |
25 |
Correct |
210 ms |
18000 KB |
Output is correct |
26 |
Correct |
230 ms |
17984 KB |
Output is correct |
27 |
Correct |
248 ms |
18072 KB |
Output is correct |
28 |
Correct |
255 ms |
18024 KB |
Output is correct |
29 |
Correct |
239 ms |
17988 KB |
Output is correct |
30 |
Correct |
124 ms |
2500 KB |
Output is correct |
31 |
Correct |
224 ms |
18048 KB |
Output is correct |
32 |
Correct |
249 ms |
17648 KB |
Output is correct |
33 |
Correct |
116 ms |
2372 KB |
Output is correct |
34 |
Correct |
245 ms |
18008 KB |
Output is correct |
35 |
Correct |
189 ms |
17024 KB |
Output is correct |
36 |
Correct |
113 ms |
2372 KB |
Output is correct |
37 |
Correct |
112 ms |
2260 KB |
Output is correct |
38 |
Correct |
276 ms |
14840 KB |
Output is correct |
39 |
Incorrect |
154 ms |
14036 KB |
Output isn't correct |
40 |
Halted |
0 ms |
0 KB |
- |