#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int nmax = 200005;
const int mod = 1e9 + 7;
const int p = 101;
int n, q, pw[nmax], tree[4*nmax], lazy[4*nmax], sump[nmax];
string Sa, Sb, Sc, T0;
map<int,int>mp;
int generatehash(string aux){
int hsh = 0;
for(int i=0;i<(int)aux.size();i++){
hsh = (hsh + pw[i] * (aux[i] - '0') % mod) % mod;
}
return hsh;
}
vector<pair<string, int>>vecc;
void calc(){
for(auto it : vecc){
mp[it.sc] = 1;
}
for(int i=0;i<(int)vecc.size();i++){
for(int j=0;j<i;j++){
string aux;
for(int t=0;t<n;t++){
if(vecc[i].fr[t] == vecc[j].fr[t]){
aux += vecc[i].fr[t];
}
else if(vecc[i].fr[t] != '1' && vecc[j].fr[t] != '1'){
aux += '1';
}
else if(vecc[i].fr[t] != '0' && vecc[j].fr[t] != '0'){
aux += '0';
}
else{
aux += '2';
}
}
int curr = generatehash(aux);
if(mp.count(curr) == 0){
mp[curr] = 1;
vecc.push_back({aux, curr});
}
}
}
}
void build(int l, int r, int nod){
if(l == r){
tree[nod] = (T0[l - 1] - '0');
}
else{
int mid = l + (r - l) / 2;
build(l, mid, 2*nod);
build(mid+1, r, 2*nod+1);
tree[nod] = (tree[2*nod] + pw[(mid - l + 1)] * tree[2*nod + 1] % mod) % mod;
}
}
void push(int l, int r, int nod){
if(lazy[nod] >= 1){
tree[nod] = (lazy[nod] - 1LL) * sump[r - l] % mod;
if(l != r){
lazy[2*nod] = lazy[nod];
lazy[2*nod+1] = lazy[nod];
}
lazy[nod] = 0;
}
}
void update(int l, int r, int le, int ri, int val, int nod){
push(l, r, nod);
if(l > ri || r < le){
return;
}
else if(l >= le && r <= ri){
lazy[nod] = val;
push(l, r, nod);
}
else{
int mid = l + (r - l) / 2;
update(l, mid, le, ri, val, 2*nod);
update(mid + 1, r, le, ri, val, 2*nod + 1);
tree[nod] = (tree[2*nod] + pw[(mid - l + 1)] * tree[2*nod + 1] % mod) % mod;
}
}
bool check(){
push(1, n, 1);
for(auto it : vecc){
if(it.sc == tree[1]){
return true;
}
}
return false;
}
int32_t main(){
//ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
// freopen("input.in", "r", stdin);
pw[0] = 1;
sump[0] = 1;
for(int i=1;i<nmax;i++){
pw[i] = pw[i-1] * p % mod;
sump[i] = (sump[i-1] + pw[i]) % mod;
}
cin >> n >> Sa >> Sb >> Sc >> q >> T0;
for(auto &it : Sa){
if(it == 'J') it = '0';
else if(it == 'O') it = '1';
else it = '2';
}
for(auto &it : Sb){
if(it == 'J') it = '0';
else if(it == 'O') it = '1';
else it = '2';
}
for(auto &it : Sc){
if(it == 'J') it = '0';
else if(it == 'O') it = '1';
else it = '2';
}
for(auto &it : T0){
if(it == 'J') it = '0';
else if(it == 'O') it = '1';
else it = '2';
}
vecc.push_back({Sa, generatehash(Sa)});
vecc.push_back({Sb, generatehash(Sb)});
vecc.push_back({Sc, generatehash(Sc)});
calc();
build(1, n, 1);
cout << (check() == true ? "Yes" : "No") << '\n';
for(int i=1;i<=q;i++){
int l, r;
char c;
cin >> l >> r >> c;
int val;
if(c == 'J') val = 1;
else if(c == 'O') val = 2;
else val = 3;
update(1, n, l, r, val, 1);
cout << (check() == true ? "Yes" : "No") << '\n';
}
}
// 1. Solve the problem
// 2. ???
// 3. Profit
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
481 ms |
3968 KB |
Output is correct |
2 |
Correct |
516 ms |
4112 KB |
Output is correct |
3 |
Correct |
508 ms |
4032 KB |
Output is correct |
4 |
Correct |
498 ms |
3956 KB |
Output is correct |
5 |
Correct |
480 ms |
3956 KB |
Output is correct |
6 |
Correct |
502 ms |
3896 KB |
Output is correct |
7 |
Correct |
520 ms |
4008 KB |
Output is correct |
8 |
Correct |
514 ms |
4032 KB |
Output is correct |
9 |
Correct |
504 ms |
3952 KB |
Output is correct |
10 |
Correct |
520 ms |
4036 KB |
Output is correct |
11 |
Correct |
492 ms |
3920 KB |
Output is correct |
12 |
Correct |
515 ms |
4016 KB |
Output is correct |
13 |
Correct |
546 ms |
4080 KB |
Output is correct |
14 |
Correct |
529 ms |
4028 KB |
Output is correct |
15 |
Correct |
532 ms |
3972 KB |
Output is correct |
16 |
Correct |
530 ms |
4056 KB |
Output is correct |
17 |
Correct |
566 ms |
3944 KB |
Output is correct |
18 |
Correct |
504 ms |
4028 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
481 ms |
3968 KB |
Output is correct |
2 |
Correct |
516 ms |
4112 KB |
Output is correct |
3 |
Correct |
508 ms |
4032 KB |
Output is correct |
4 |
Correct |
498 ms |
3956 KB |
Output is correct |
5 |
Correct |
480 ms |
3956 KB |
Output is correct |
6 |
Correct |
502 ms |
3896 KB |
Output is correct |
7 |
Correct |
520 ms |
4008 KB |
Output is correct |
8 |
Correct |
514 ms |
4032 KB |
Output is correct |
9 |
Correct |
504 ms |
3952 KB |
Output is correct |
10 |
Correct |
520 ms |
4036 KB |
Output is correct |
11 |
Correct |
492 ms |
3920 KB |
Output is correct |
12 |
Correct |
515 ms |
4016 KB |
Output is correct |
13 |
Correct |
546 ms |
4080 KB |
Output is correct |
14 |
Correct |
529 ms |
4028 KB |
Output is correct |
15 |
Correct |
532 ms |
3972 KB |
Output is correct |
16 |
Correct |
530 ms |
4056 KB |
Output is correct |
17 |
Correct |
566 ms |
3944 KB |
Output is correct |
18 |
Correct |
504 ms |
4028 KB |
Output is correct |
19 |
Correct |
6589 ms |
14156 KB |
Output is correct |
20 |
Correct |
6345 ms |
10816 KB |
Output is correct |
21 |
Correct |
5765 ms |
13976 KB |
Output is correct |
22 |
Correct |
5091 ms |
13860 KB |
Output is correct |
23 |
Correct |
880 ms |
4676 KB |
Output is correct |
24 |
Correct |
896 ms |
4584 KB |
Output is correct |
25 |
Correct |
6323 ms |
14460 KB |
Output is correct |
26 |
Correct |
6327 ms |
14280 KB |
Output is correct |
27 |
Correct |
6452 ms |
14232 KB |
Output is correct |
28 |
Correct |
6420 ms |
14128 KB |
Output is correct |
29 |
Correct |
6042 ms |
14124 KB |
Output is correct |
30 |
Correct |
884 ms |
4820 KB |
Output is correct |
31 |
Correct |
6452 ms |
14068 KB |
Output is correct |
32 |
Correct |
5656 ms |
14020 KB |
Output is correct |
33 |
Correct |
896 ms |
4768 KB |
Output is correct |
34 |
Correct |
6420 ms |
14344 KB |
Output is correct |
35 |
Correct |
4498 ms |
13764 KB |
Output is correct |
36 |
Correct |
895 ms |
4608 KB |
Output is correct |
37 |
Correct |
886 ms |
4644 KB |
Output is correct |
38 |
Correct |
5945 ms |
10896 KB |
Output is correct |
39 |
Correct |
5952 ms |
9940 KB |
Output is correct |
40 |
Correct |
4376 ms |
9364 KB |
Output is correct |
41 |
Correct |
2893 ms |
14140 KB |
Output is correct |
42 |
Correct |
2394 ms |
10096 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
481 ms |
3968 KB |
Output is correct |
2 |
Correct |
516 ms |
4112 KB |
Output is correct |
3 |
Correct |
508 ms |
4032 KB |
Output is correct |
4 |
Correct |
498 ms |
3956 KB |
Output is correct |
5 |
Correct |
480 ms |
3956 KB |
Output is correct |
6 |
Correct |
502 ms |
3896 KB |
Output is correct |
7 |
Correct |
520 ms |
4008 KB |
Output is correct |
8 |
Correct |
514 ms |
4032 KB |
Output is correct |
9 |
Correct |
504 ms |
3952 KB |
Output is correct |
10 |
Correct |
520 ms |
4036 KB |
Output is correct |
11 |
Correct |
492 ms |
3920 KB |
Output is correct |
12 |
Correct |
515 ms |
4016 KB |
Output is correct |
13 |
Correct |
546 ms |
4080 KB |
Output is correct |
14 |
Correct |
529 ms |
4028 KB |
Output is correct |
15 |
Correct |
532 ms |
3972 KB |
Output is correct |
16 |
Correct |
530 ms |
4056 KB |
Output is correct |
17 |
Correct |
566 ms |
3944 KB |
Output is correct |
18 |
Correct |
504 ms |
4028 KB |
Output is correct |
19 |
Correct |
570 ms |
3960 KB |
Output is correct |
20 |
Correct |
579 ms |
3992 KB |
Output is correct |
21 |
Correct |
544 ms |
4012 KB |
Output is correct |
22 |
Correct |
537 ms |
3948 KB |
Output is correct |
23 |
Correct |
524 ms |
3992 KB |
Output is correct |
24 |
Correct |
508 ms |
4008 KB |
Output is correct |
25 |
Correct |
505 ms |
4004 KB |
Output is correct |
26 |
Correct |
499 ms |
4016 KB |
Output is correct |
27 |
Correct |
506 ms |
4004 KB |
Output is correct |
28 |
Correct |
472 ms |
4092 KB |
Output is correct |
29 |
Correct |
494 ms |
4036 KB |
Output is correct |
30 |
Correct |
480 ms |
3996 KB |
Output is correct |
31 |
Correct |
546 ms |
4036 KB |
Output is correct |
32 |
Correct |
548 ms |
3976 KB |
Output is correct |
33 |
Correct |
564 ms |
3996 KB |
Output is correct |
34 |
Correct |
538 ms |
3888 KB |
Output is correct |
35 |
Correct |
544 ms |
3960 KB |
Output is correct |
36 |
Correct |
546 ms |
4024 KB |
Output is correct |
37 |
Correct |
545 ms |
4036 KB |
Output is correct |
38 |
Correct |
551 ms |
4180 KB |
Output is correct |
39 |
Correct |
551 ms |
4036 KB |
Output is correct |
40 |
Correct |
541 ms |
4028 KB |
Output is correct |
41 |
Correct |
550 ms |
4092 KB |
Output is correct |
42 |
Correct |
548 ms |
4072 KB |
Output is correct |
43 |
Correct |
530 ms |
4012 KB |
Output is correct |
44 |
Correct |
561 ms |
3964 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
481 ms |
3968 KB |
Output is correct |
2 |
Correct |
516 ms |
4112 KB |
Output is correct |
3 |
Correct |
508 ms |
4032 KB |
Output is correct |
4 |
Correct |
498 ms |
3956 KB |
Output is correct |
5 |
Correct |
480 ms |
3956 KB |
Output is correct |
6 |
Correct |
502 ms |
3896 KB |
Output is correct |
7 |
Correct |
520 ms |
4008 KB |
Output is correct |
8 |
Correct |
514 ms |
4032 KB |
Output is correct |
9 |
Correct |
504 ms |
3952 KB |
Output is correct |
10 |
Correct |
520 ms |
4036 KB |
Output is correct |
11 |
Correct |
492 ms |
3920 KB |
Output is correct |
12 |
Correct |
515 ms |
4016 KB |
Output is correct |
13 |
Correct |
546 ms |
4080 KB |
Output is correct |
14 |
Correct |
529 ms |
4028 KB |
Output is correct |
15 |
Correct |
532 ms |
3972 KB |
Output is correct |
16 |
Correct |
530 ms |
4056 KB |
Output is correct |
17 |
Correct |
566 ms |
3944 KB |
Output is correct |
18 |
Correct |
504 ms |
4028 KB |
Output is correct |
19 |
Correct |
6589 ms |
14156 KB |
Output is correct |
20 |
Correct |
6345 ms |
10816 KB |
Output is correct |
21 |
Correct |
5765 ms |
13976 KB |
Output is correct |
22 |
Correct |
5091 ms |
13860 KB |
Output is correct |
23 |
Correct |
880 ms |
4676 KB |
Output is correct |
24 |
Correct |
896 ms |
4584 KB |
Output is correct |
25 |
Correct |
6323 ms |
14460 KB |
Output is correct |
26 |
Correct |
6327 ms |
14280 KB |
Output is correct |
27 |
Correct |
6452 ms |
14232 KB |
Output is correct |
28 |
Correct |
6420 ms |
14128 KB |
Output is correct |
29 |
Correct |
6042 ms |
14124 KB |
Output is correct |
30 |
Correct |
884 ms |
4820 KB |
Output is correct |
31 |
Correct |
6452 ms |
14068 KB |
Output is correct |
32 |
Correct |
5656 ms |
14020 KB |
Output is correct |
33 |
Correct |
896 ms |
4768 KB |
Output is correct |
34 |
Correct |
6420 ms |
14344 KB |
Output is correct |
35 |
Correct |
4498 ms |
13764 KB |
Output is correct |
36 |
Correct |
895 ms |
4608 KB |
Output is correct |
37 |
Correct |
886 ms |
4644 KB |
Output is correct |
38 |
Correct |
5945 ms |
10896 KB |
Output is correct |
39 |
Correct |
5952 ms |
9940 KB |
Output is correct |
40 |
Correct |
4376 ms |
9364 KB |
Output is correct |
41 |
Correct |
2893 ms |
14140 KB |
Output is correct |
42 |
Correct |
2394 ms |
10096 KB |
Output is correct |
43 |
Correct |
570 ms |
3960 KB |
Output is correct |
44 |
Correct |
579 ms |
3992 KB |
Output is correct |
45 |
Correct |
544 ms |
4012 KB |
Output is correct |
46 |
Correct |
537 ms |
3948 KB |
Output is correct |
47 |
Correct |
524 ms |
3992 KB |
Output is correct |
48 |
Correct |
508 ms |
4008 KB |
Output is correct |
49 |
Correct |
505 ms |
4004 KB |
Output is correct |
50 |
Correct |
499 ms |
4016 KB |
Output is correct |
51 |
Correct |
506 ms |
4004 KB |
Output is correct |
52 |
Correct |
472 ms |
4092 KB |
Output is correct |
53 |
Correct |
494 ms |
4036 KB |
Output is correct |
54 |
Correct |
480 ms |
3996 KB |
Output is correct |
55 |
Correct |
546 ms |
4036 KB |
Output is correct |
56 |
Correct |
548 ms |
3976 KB |
Output is correct |
57 |
Correct |
564 ms |
3996 KB |
Output is correct |
58 |
Correct |
538 ms |
3888 KB |
Output is correct |
59 |
Correct |
544 ms |
3960 KB |
Output is correct |
60 |
Correct |
546 ms |
4024 KB |
Output is correct |
61 |
Correct |
545 ms |
4036 KB |
Output is correct |
62 |
Correct |
551 ms |
4180 KB |
Output is correct |
63 |
Correct |
551 ms |
4036 KB |
Output is correct |
64 |
Correct |
541 ms |
4028 KB |
Output is correct |
65 |
Correct |
550 ms |
4092 KB |
Output is correct |
66 |
Correct |
548 ms |
4072 KB |
Output is correct |
67 |
Correct |
530 ms |
4012 KB |
Output is correct |
68 |
Correct |
561 ms |
3964 KB |
Output is correct |
69 |
Execution timed out |
7029 ms |
15104 KB |
Time limit exceeded |
70 |
Halted |
0 ms |
0 KB |
- |