// 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+3;
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 |
83 ms |
964 KB |
Output is correct |
2 |
Correct |
83 ms |
868 KB |
Output is correct |
3 |
Correct |
87 ms |
856 KB |
Output is correct |
4 |
Correct |
69 ms |
808 KB |
Output is correct |
5 |
Correct |
81 ms |
796 KB |
Output is correct |
6 |
Correct |
70 ms |
780 KB |
Output is correct |
7 |
Correct |
74 ms |
912 KB |
Output is correct |
8 |
Correct |
72 ms |
856 KB |
Output is correct |
9 |
Correct |
74 ms |
852 KB |
Output is correct |
10 |
Correct |
71 ms |
836 KB |
Output is correct |
11 |
Correct |
75 ms |
852 KB |
Output is correct |
12 |
Correct |
72 ms |
828 KB |
Output is correct |
13 |
Correct |
73 ms |
904 KB |
Output is correct |
14 |
Correct |
71 ms |
944 KB |
Output is correct |
15 |
Correct |
83 ms |
940 KB |
Output is correct |
16 |
Correct |
73 ms |
900 KB |
Output is correct |
17 |
Correct |
77 ms |
940 KB |
Output is correct |
18 |
Correct |
83 ms |
960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
964 KB |
Output is correct |
2 |
Correct |
83 ms |
868 KB |
Output is correct |
3 |
Correct |
87 ms |
856 KB |
Output is correct |
4 |
Correct |
69 ms |
808 KB |
Output is correct |
5 |
Correct |
81 ms |
796 KB |
Output is correct |
6 |
Correct |
70 ms |
780 KB |
Output is correct |
7 |
Correct |
74 ms |
912 KB |
Output is correct |
8 |
Correct |
72 ms |
856 KB |
Output is correct |
9 |
Correct |
74 ms |
852 KB |
Output is correct |
10 |
Correct |
71 ms |
836 KB |
Output is correct |
11 |
Correct |
75 ms |
852 KB |
Output is correct |
12 |
Correct |
72 ms |
828 KB |
Output is correct |
13 |
Correct |
73 ms |
904 KB |
Output is correct |
14 |
Correct |
71 ms |
944 KB |
Output is correct |
15 |
Correct |
83 ms |
940 KB |
Output is correct |
16 |
Correct |
73 ms |
900 KB |
Output is correct |
17 |
Correct |
77 ms |
940 KB |
Output is correct |
18 |
Correct |
83 ms |
960 KB |
Output is correct |
19 |
Correct |
343 ms |
17584 KB |
Output is correct |
20 |
Correct |
348 ms |
14400 KB |
Output is correct |
21 |
Correct |
180 ms |
17304 KB |
Output is correct |
22 |
Correct |
186 ms |
16928 KB |
Output is correct |
23 |
Correct |
121 ms |
1992 KB |
Output is correct |
24 |
Correct |
114 ms |
1864 KB |
Output is correct |
25 |
Correct |
242 ms |
17540 KB |
Output is correct |
26 |
Correct |
227 ms |
17756 KB |
Output is correct |
27 |
Correct |
230 ms |
17600 KB |
Output is correct |
28 |
Correct |
252 ms |
17644 KB |
Output is correct |
29 |
Correct |
206 ms |
17500 KB |
Output is correct |
30 |
Correct |
134 ms |
1880 KB |
Output is correct |
31 |
Correct |
207 ms |
17612 KB |
Output is correct |
32 |
Correct |
274 ms |
17256 KB |
Output is correct |
33 |
Correct |
120 ms |
1848 KB |
Output is correct |
34 |
Correct |
249 ms |
17564 KB |
Output is correct |
35 |
Correct |
184 ms |
16524 KB |
Output is correct |
36 |
Correct |
162 ms |
1908 KB |
Output is correct |
37 |
Correct |
112 ms |
1912 KB |
Output is correct |
38 |
Correct |
255 ms |
14640 KB |
Output is correct |
39 |
Incorrect |
140 ms |
13544 KB |
Output isn't correct |
40 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
964 KB |
Output is correct |
2 |
Correct |
83 ms |
868 KB |
Output is correct |
3 |
Correct |
87 ms |
856 KB |
Output is correct |
4 |
Correct |
69 ms |
808 KB |
Output is correct |
5 |
Correct |
81 ms |
796 KB |
Output is correct |
6 |
Correct |
70 ms |
780 KB |
Output is correct |
7 |
Correct |
74 ms |
912 KB |
Output is correct |
8 |
Correct |
72 ms |
856 KB |
Output is correct |
9 |
Correct |
74 ms |
852 KB |
Output is correct |
10 |
Correct |
71 ms |
836 KB |
Output is correct |
11 |
Correct |
75 ms |
852 KB |
Output is correct |
12 |
Correct |
72 ms |
828 KB |
Output is correct |
13 |
Correct |
73 ms |
904 KB |
Output is correct |
14 |
Correct |
71 ms |
944 KB |
Output is correct |
15 |
Correct |
83 ms |
940 KB |
Output is correct |
16 |
Correct |
73 ms |
900 KB |
Output is correct |
17 |
Correct |
77 ms |
940 KB |
Output is correct |
18 |
Correct |
83 ms |
960 KB |
Output is correct |
19 |
Correct |
81 ms |
840 KB |
Output is correct |
20 |
Correct |
90 ms |
944 KB |
Output is correct |
21 |
Correct |
76 ms |
828 KB |
Output is correct |
22 |
Correct |
63 ms |
832 KB |
Output is correct |
23 |
Correct |
73 ms |
876 KB |
Output is correct |
24 |
Correct |
71 ms |
904 KB |
Output is correct |
25 |
Correct |
72 ms |
820 KB |
Output is correct |
26 |
Correct |
88 ms |
884 KB |
Output is correct |
27 |
Correct |
73 ms |
876 KB |
Output is correct |
28 |
Correct |
67 ms |
848 KB |
Output is correct |
29 |
Correct |
94 ms |
916 KB |
Output is correct |
30 |
Correct |
68 ms |
836 KB |
Output is correct |
31 |
Correct |
75 ms |
836 KB |
Output is correct |
32 |
Correct |
73 ms |
964 KB |
Output is correct |
33 |
Correct |
76 ms |
832 KB |
Output is correct |
34 |
Correct |
72 ms |
836 KB |
Output is correct |
35 |
Correct |
74 ms |
824 KB |
Output is correct |
36 |
Correct |
74 ms |
936 KB |
Output is correct |
37 |
Correct |
83 ms |
992 KB |
Output is correct |
38 |
Correct |
92 ms |
832 KB |
Output is correct |
39 |
Correct |
73 ms |
836 KB |
Output is correct |
40 |
Correct |
73 ms |
876 KB |
Output is correct |
41 |
Correct |
75 ms |
936 KB |
Output is correct |
42 |
Correct |
73 ms |
868 KB |
Output is correct |
43 |
Correct |
70 ms |
848 KB |
Output is correct |
44 |
Correct |
88 ms |
888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
964 KB |
Output is correct |
2 |
Correct |
83 ms |
868 KB |
Output is correct |
3 |
Correct |
87 ms |
856 KB |
Output is correct |
4 |
Correct |
69 ms |
808 KB |
Output is correct |
5 |
Correct |
81 ms |
796 KB |
Output is correct |
6 |
Correct |
70 ms |
780 KB |
Output is correct |
7 |
Correct |
74 ms |
912 KB |
Output is correct |
8 |
Correct |
72 ms |
856 KB |
Output is correct |
9 |
Correct |
74 ms |
852 KB |
Output is correct |
10 |
Correct |
71 ms |
836 KB |
Output is correct |
11 |
Correct |
75 ms |
852 KB |
Output is correct |
12 |
Correct |
72 ms |
828 KB |
Output is correct |
13 |
Correct |
73 ms |
904 KB |
Output is correct |
14 |
Correct |
71 ms |
944 KB |
Output is correct |
15 |
Correct |
83 ms |
940 KB |
Output is correct |
16 |
Correct |
73 ms |
900 KB |
Output is correct |
17 |
Correct |
77 ms |
940 KB |
Output is correct |
18 |
Correct |
83 ms |
960 KB |
Output is correct |
19 |
Correct |
343 ms |
17584 KB |
Output is correct |
20 |
Correct |
348 ms |
14400 KB |
Output is correct |
21 |
Correct |
180 ms |
17304 KB |
Output is correct |
22 |
Correct |
186 ms |
16928 KB |
Output is correct |
23 |
Correct |
121 ms |
1992 KB |
Output is correct |
24 |
Correct |
114 ms |
1864 KB |
Output is correct |
25 |
Correct |
242 ms |
17540 KB |
Output is correct |
26 |
Correct |
227 ms |
17756 KB |
Output is correct |
27 |
Correct |
230 ms |
17600 KB |
Output is correct |
28 |
Correct |
252 ms |
17644 KB |
Output is correct |
29 |
Correct |
206 ms |
17500 KB |
Output is correct |
30 |
Correct |
134 ms |
1880 KB |
Output is correct |
31 |
Correct |
207 ms |
17612 KB |
Output is correct |
32 |
Correct |
274 ms |
17256 KB |
Output is correct |
33 |
Correct |
120 ms |
1848 KB |
Output is correct |
34 |
Correct |
249 ms |
17564 KB |
Output is correct |
35 |
Correct |
184 ms |
16524 KB |
Output is correct |
36 |
Correct |
162 ms |
1908 KB |
Output is correct |
37 |
Correct |
112 ms |
1912 KB |
Output is correct |
38 |
Correct |
255 ms |
14640 KB |
Output is correct |
39 |
Incorrect |
140 ms |
13544 KB |
Output isn't correct |
40 |
Halted |
0 ms |
0 KB |
- |