#include <bits/stdc++.h>
#define hmod 1223334444555553LL
using namespace std;
int sz,n,nowl,nowr,l[200005],r[200005],q,blk;
long long val,sum[505],ttl,b[200005],sumb[505],indx[200005],all[505],nowindx;
char c[10]={'a','J','O','I'},ch;
string s,str;
vector <string> v;
map <string,bool> a;
map <long long,bool> hashing;
void makestring(){
for (int i=0;i<v.size();i++){
for (int j=i+1;j<v.size();j++){
str.clear();
for (int k=0;k<n;k++){
if (v[i][k] != v[j][k]){
for (int l=1;l<=3;l++){
if (c[l] != v[i][k] && c[l] != v[j][k])
str+=c[l];
}
}
else
str+=v[i][k];
}
if (!a[str]){
v.push_back(str);
a[str]=true;
}
}
}
for (int i=0;i<v.size();i++){
val=0;
for (int j=0;j<n;j++){
for (long long k=1;k<=3;k++){
if (v[i][j] == c[k])
val+=k*b[j];
}
val%=hmod;
}
// cerr << val << " " << v[i] << "\n";
hashing[val]=true;
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cout.tie(0);
cin >> n;
for (int i=1;i<=3;i++){
cin >> s;
a[s]=true; v.push_back(s);
}
b[0]=1;
for (int i=1;i<n;i++){
b[i]=b[i-1]*4;
b[i]%=hmod;
}
makestring();
sz=int(sqrt(n));
if (sz*sz != n) sz++;
nowl=0; nowr=sz-1;
for (int i=1;i<=sz;i++){
l[i]=nowl; r[i]=nowr;
nowl=nowr+1; nowr=min(n-1,nowl+sz-1);
if (nowl >= n){
sz=i;
break;
}
}
cin >> q >> str;
for (int i=0;i<n;i++){
for (int j=1;j<=3;j++){
if (str[i] == c[j])
indx[i]=j;
}
}
for (int i=1;i<=sz;i++){
for (int j=l[i];j<=r[i];j++){
sum[i]+=indx[j]*b[j]; sum[i]%=hmod;
sumb[i]+=b[j]; sumb[i]%=hmod;
}
ttl+=sum[i]; ttl%=hmod;
all[i]=-1;
}
// cerr << ttl << "\n";
if (hashing[ttl]) cout << "Yes\n";
else cout << "No\n";
for (int i=1;i<=q;i++){
cin >> nowl >> nowr >> ch;
nowl--; nowr--;
ttl=0;
for (int j=1;j<=3;j++){
if (ch == c[j]) nowindx=j;
}
for (int j=1;j<=sz;j++){
if (nowl > r[j] || nowr < l[j])
continue;
if (nowl <= l[j] && r[j] <= nowr){
all[j]=nowindx;
sum[j]=nowindx*sumb[j];
}
else
if (l[j] <= nowl && nowl <= r[j]){
if (all[j] == -1){
for (int k=nowl;k<=min(nowl,r[j]);k++){
sum[j]-=b[k]*indx[k]; sum[j]+=b[k]*nowindx;
indx[k]=nowindx;
}
}
else
{
for (int k=l[j];k<nowl;k++){
indx[k]=all[j];
}
for (int k=nowl;k<=min(nowr,r[j]);k++){
sum[j]-=b[k]*all[j]; sum[j]+=b[k]*nowindx;
indx[k]=nowindx;
}
for (int k=min(nowr,r[j])+1;k<=r[j];k++){
indx[k]=all[j];
}
}
all[j]=-1;
}
else
if (l[j] <= nowr && nowr <= r[j]){
if (all[j] == -1){
for (int k=max(nowl,l[j]);k<=nowr;k++){
sum[j]-=b[k]*indx[k]; sum[j]+=b[k]*nowindx;
indx[k]=nowindx;
}
}
else
{
for (int k=l[j];k<max(nowl,l[j]);k++){
indx[k]=all[j];
}
for (int k=max(nowl,l[j]);k<=nowr;k++){
sum[j]-=b[k]*all[j]; sum[j]+=b[k]*nowindx;
indx[k]=nowindx;
}
for (int k=nowr+1;k<=r[j];k++){
indx[k]=all[j];
}
}
all[j]=-1;
}
while (sum[j] < 0) sum[j]+=hmod;
}
for (int j=1;j<=sz;j++){
ttl+=sum[j]; ttl%=hmod;
}
// cerr << ttl << "\n";
if (hashing[ttl]) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
Compilation message
Main.cpp: In function 'void makestring()':
Main.cpp:13:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for (int i=0;i<v.size();i++){
| ~^~~~~~~~~
Main.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for (int j=i+1;j<v.size();j++){
| ~^~~~~~~~~
Main.cpp:32:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int i=0;i<v.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
158 ms |
10204 KB |
Output is correct |
| 2 |
Correct |
167 ms |
11084 KB |
Output is correct |
| 3 |
Correct |
144 ms |
9016 KB |
Output is correct |
| 4 |
Incorrect |
146 ms |
10600 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
158 ms |
10204 KB |
Output is correct |
| 2 |
Correct |
167 ms |
11084 KB |
Output is correct |
| 3 |
Correct |
144 ms |
9016 KB |
Output is correct |
| 4 |
Incorrect |
146 ms |
10600 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
158 ms |
10204 KB |
Output is correct |
| 2 |
Correct |
167 ms |
11084 KB |
Output is correct |
| 3 |
Correct |
144 ms |
9016 KB |
Output is correct |
| 4 |
Incorrect |
146 ms |
10600 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
158 ms |
10204 KB |
Output is correct |
| 2 |
Correct |
167 ms |
11084 KB |
Output is correct |
| 3 |
Correct |
144 ms |
9016 KB |
Output is correct |
| 4 |
Incorrect |
146 ms |
10600 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
