#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxN = 2e5 + 7;
const int SZ = exp2(ceil(log2(mxN)));
const int MOD[] = {1000000007, 252099000000ll};
int n, p[mxN][2], num[130], seg[4*mxN][2], lazy[4*mxN], def[mxN][2];
string cross(string a, string b) {
string res;
for (int i = 0; i < n; ++i) {
if (a[i] == b[i]) {
res += a[i];
continue;
}
set<char> ch;
ch.insert(a[i]);
ch.insert(b[i]);
for (auto c : {'J', 'O', 'I'}) {
if (!ch.count(c)) {
res += c;
break;
}
}
}
return res;
}
void push(int ind, int l, int r, int cnt=1) {
if (!lazy[ind]) {
return;
}
for (auto id : {0, 1}) {
seg[ind][id] = (def[r][id] - (l ? def[l-1][id] : 0)) * lazy[ind] % MOD[id];
}
if (l != r) {
lazy[2*ind] = lazy[ind];
lazy[2*ind+1] = lazy[ind];
if (cnt) {
int mid = (l+r)/2;
push(2*ind,l,mid,cnt-1);
push(2*ind+1,mid+1,r,cnt-1);
}
}
lazy[ind] = 0;
}
void update(int lo, int hi, int val, int ind=1, int l=0, int r=SZ-1) {
push(ind,l,r);
if (lo > r || l > hi) {
return;
}
if (lo <= l && r <= hi) {
lazy[ind] = val;
push(ind,l,r);
return;
}
int mid = (l+r)/2;
update(lo,hi,val,2*ind,l,mid);
update(lo,hi,val,2*ind+1,mid+1,r);
for (auto id : {0, 1}) {
seg[ind][id] = (seg[2*ind][id] + seg[2*ind+1][id]) % MOD[id];
}
}
int query(int lo, int hi, int id, int ind=1, int l=0, int r=SZ-1) {
push(ind,l,r);
if (lo > r || l > hi) {
return 0;
}
if (lo <= l && r <= hi) {
return seg[ind][id];
}
int mid = (l+r)/2;
return (query(lo,hi,id,2*ind,l,mid)+query(lo,hi,id,2*ind+1,mid+1,r)) % MOD[id];
}
int hsh(string s, int id) {
int res = 0;
for (int i = 0; i < n; ++i) {
res += num[s[i]] * p[i][id] % MOD[id];
res %= MOD[id];
}
return res;
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
num['J'] = 1, num['O'] = 2, num['I'] = 3;
p[0][0] = p[0][1] = 1;;
for (int i = 1; i < n; ++i) {
p[i][0] = p[i-1][0] * 31 % MOD[0];
p[i][1] = p[i-1][1] * 73 % MOD[1];
}
set<string> check;
vector<string> s;
for (int i = 0; i < 3; ++i) {
string str;
cin >> str;
if (!check.count(str)) {
s.push_back(str);
check.insert(str);
}
}
int ind = 0;
while (ind < s.size()) {
int len = s.size();
for (int i = 0; i < len; ++i) {
string str = cross(s[ind], s[i]);
if (!check.count(str)) {
s.push_back(str);
check.insert(str);
}
}
++ind;
}
set<int> fin[2];
for (int i = 0; i < s.size(); ++i) {
for (auto id : {0, 1}) {
fin[id].insert(hsh(s[i],id));
}
}
int q;
cin >> q;
string t;
cin >> t;
def[0][0] = def[0][1] = 1;
seg[SZ][0] = seg[SZ][1] = num[t[0]];
for (int i = 1; i < n; ++i) {
for (auto id : {0, 1}) {
def[i][id] = (def[i-1][id] + p[i][id]) % MOD[id];
seg[i+SZ][id] = num[t[i]] * p[i][id] % MOD[id];
}
}
for (int i = SZ-1; i >= 0; --i) {
for (auto id : {0, 1}) {
seg[i][id] = (seg[2*i][id] + seg[2*i+1][id]) % MOD[id];
}
}
int cnt = 1;
cout << (fin[0].count(query(0,n-1,0)) && fin[1].count(query(0,n-1,1)) ?
"Yes\n" : "No\n");
while (q--) {
int l, r;
char c;
cin >> l >> r >> c;
--l, --r;
update(l, r, num[c]);
cout << (fin[0].count(query(0,n-1,0)) && fin[1].count(query(0,n-1,1)) ?
"Yes\n" : "No\n");
}
}
Compilation message
Main.cpp: In function 'long long int hsh(std::string, long long int)':
Main.cpp:94:24: warning: array subscript has type 'char' [-Wchar-subscripts]
94 | res += num[s[i]] * p[i][id] % MOD[id];
| ^
Main.cpp: In function 'int32_t main()':
Main.cpp:125:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | while (ind < s.size()) {
| ~~~~^~~~~~~~~~
Main.cpp:138:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for (int i = 0; i < s.size(); ++i) {
| ~~^~~~~~~~~~
Main.cpp:151:39: warning: array subscript has type 'char' [-Wchar-subscripts]
151 | seg[SZ][0] = seg[SZ][1] = num[t[0]];
| ^
Main.cpp:155:37: warning: array subscript has type 'char' [-Wchar-subscripts]
155 | seg[i+SZ][id] = num[t[i]] * p[i][id] % MOD[id];
| ^
Main.cpp:174:26: warning: array subscript has type 'char' [-Wchar-subscripts]
174 | update(l, r, num[c]);
| ^
Main.cpp:165:9: warning: unused variable 'cnt' [-Wunused-variable]
165 | int cnt = 1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
10436 KB |
Output is correct |
| 2 |
Correct |
156 ms |
10804 KB |
Output is correct |
| 3 |
Correct |
160 ms |
12612 KB |
Output is correct |
| 4 |
Incorrect |
152 ms |
10608 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
10436 KB |
Output is correct |
| 2 |
Correct |
156 ms |
10804 KB |
Output is correct |
| 3 |
Correct |
160 ms |
12612 KB |
Output is correct |
| 4 |
Incorrect |
152 ms |
10608 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
10436 KB |
Output is correct |
| 2 |
Correct |
156 ms |
10804 KB |
Output is correct |
| 3 |
Correct |
160 ms |
12612 KB |
Output is correct |
| 4 |
Incorrect |
152 ms |
10608 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
10436 KB |
Output is correct |
| 2 |
Correct |
156 ms |
10804 KB |
Output is correct |
| 3 |
Correct |
160 ms |
12612 KB |
Output is correct |
| 4 |
Incorrect |
152 ms |
10608 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
