#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
mt19937 _rand(time(NULL));
const int mxn = 2e5 + 5;
ll A = 911382323;
ll B = 972663749;
ll pre[3][mxn];
ll seg[4*mxn];
int z[4*mxn];
ll p[mxn];
char alp[3] = {'O', 'I', 'J'};
void upd(int k, int l, int r){
if(z[k] != 0){
seg[k] = pre[z[k]-1][r-l+1];
}
else{
int mid = (l+r)/2;
seg[k] = (((seg[k*2] * p[r-mid]) % B) + seg[k*2+1])%B;
}
}
void push(int k){
if(z[k] == 0) return;
z[k*2] = z[k*2+1] = z[k];
z[k] = 0;
}
void update(int k, int l, int r, int x, int y, int c){
if(r < x || l < y){
if(z[k] != 0) upd(k, l, r);
return;
}
if(x <= l && r <= x){
z[k] = c;
upd(k, l, r);
return;
}
push(k);
int mid = (l+r)/2;
update(k*2, l, mid, x, y, c);
update(k*2+1, mid+1, r, x, y, c);
upd(k, l, r);
}
int n;
string s[mxn];
unordered_map<string, bool> dict;
bool cross(int a, int b, int &m){
string ns;
ns.resize(n);
fr(i, 0, n){
if(s[a][i] == s[b][i]){
ns[i] = s[a][i];
}
else{
fr(j, 0, 3){
if(alp[j] != s[a][i] && alp[j] != s[b][i]){
ns[i] = alp[j];
break;
}
}
}
}
if(!dict[ns]){
dict[ns] = true;
s[m++] = ns;
return true;
}
return false;
}
void solve(){
cin >> n;
fr(i, 0, 3){
cin >> s[i];
}
int m = 3;
for(int i = 1; i < m; i ++){
fr(j, 0, i){
cross(i, j, m);
}
}
int q;
string t;
cin >> q;
cin >> t;
if(dict[t]) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
while(q--){
int l, r;
char C;
cin >> l >> r >> C;
fr(i, l-1, r) t[i] = C;
if(dict[t]) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
int main(){
p[0] = 1;
fr(i, 1, mxn){
p[i] = (p[i-1]*A) % B;
}
fr(k, 0, 3){
pre[k][0] = 1;
fr(i, 1, mxn){
pre[k][i] = (pre[k][i-1]*A + (int)alp[k])%B;
}
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
565 ms |
39568 KB |
Output is correct |
2 |
Correct |
541 ms |
44244 KB |
Output is correct |
3 |
Correct |
585 ms |
25504 KB |
Output is correct |
4 |
Correct |
519 ms |
44140 KB |
Output is correct |
5 |
Correct |
515 ms |
44512 KB |
Output is correct |
6 |
Correct |
546 ms |
42192 KB |
Output is correct |
7 |
Correct |
590 ms |
40592 KB |
Output is correct |
8 |
Correct |
520 ms |
45088 KB |
Output is correct |
9 |
Correct |
575 ms |
43924 KB |
Output is correct |
10 |
Correct |
599 ms |
49540 KB |
Output is correct |
11 |
Correct |
587 ms |
45988 KB |
Output is correct |
12 |
Correct |
590 ms |
49428 KB |
Output is correct |
13 |
Correct |
562 ms |
45928 KB |
Output is correct |
14 |
Correct |
605 ms |
49544 KB |
Output is correct |
15 |
Correct |
533 ms |
45956 KB |
Output is correct |
16 |
Correct |
615 ms |
49540 KB |
Output is correct |
17 |
Correct |
625 ms |
46048 KB |
Output is correct |
18 |
Correct |
495 ms |
20512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
565 ms |
39568 KB |
Output is correct |
2 |
Correct |
541 ms |
44244 KB |
Output is correct |
3 |
Correct |
585 ms |
25504 KB |
Output is correct |
4 |
Correct |
519 ms |
44140 KB |
Output is correct |
5 |
Correct |
515 ms |
44512 KB |
Output is correct |
6 |
Correct |
546 ms |
42192 KB |
Output is correct |
7 |
Correct |
590 ms |
40592 KB |
Output is correct |
8 |
Correct |
520 ms |
45088 KB |
Output is correct |
9 |
Correct |
575 ms |
43924 KB |
Output is correct |
10 |
Correct |
599 ms |
49540 KB |
Output is correct |
11 |
Correct |
587 ms |
45988 KB |
Output is correct |
12 |
Correct |
590 ms |
49428 KB |
Output is correct |
13 |
Correct |
562 ms |
45928 KB |
Output is correct |
14 |
Correct |
605 ms |
49544 KB |
Output is correct |
15 |
Correct |
533 ms |
45956 KB |
Output is correct |
16 |
Correct |
615 ms |
49540 KB |
Output is correct |
17 |
Correct |
625 ms |
46048 KB |
Output is correct |
18 |
Correct |
495 ms |
20512 KB |
Output is correct |
19 |
Runtime error |
1333 ms |
1048580 KB |
Execution killed with signal 9 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
565 ms |
39568 KB |
Output is correct |
2 |
Correct |
541 ms |
44244 KB |
Output is correct |
3 |
Correct |
585 ms |
25504 KB |
Output is correct |
4 |
Correct |
519 ms |
44140 KB |
Output is correct |
5 |
Correct |
515 ms |
44512 KB |
Output is correct |
6 |
Correct |
546 ms |
42192 KB |
Output is correct |
7 |
Correct |
590 ms |
40592 KB |
Output is correct |
8 |
Correct |
520 ms |
45088 KB |
Output is correct |
9 |
Correct |
575 ms |
43924 KB |
Output is correct |
10 |
Correct |
599 ms |
49540 KB |
Output is correct |
11 |
Correct |
587 ms |
45988 KB |
Output is correct |
12 |
Correct |
590 ms |
49428 KB |
Output is correct |
13 |
Correct |
562 ms |
45928 KB |
Output is correct |
14 |
Correct |
605 ms |
49544 KB |
Output is correct |
15 |
Correct |
533 ms |
45956 KB |
Output is correct |
16 |
Correct |
615 ms |
49540 KB |
Output is correct |
17 |
Correct |
625 ms |
46048 KB |
Output is correct |
18 |
Correct |
495 ms |
20512 KB |
Output is correct |
19 |
Correct |
546 ms |
42896 KB |
Output is correct |
20 |
Correct |
526 ms |
25608 KB |
Output is correct |
21 |
Correct |
661 ms |
48736 KB |
Output is correct |
22 |
Correct |
508 ms |
36468 KB |
Output is correct |
23 |
Correct |
743 ms |
48868 KB |
Output is correct |
24 |
Correct |
594 ms |
43512 KB |
Output is correct |
25 |
Correct |
681 ms |
48836 KB |
Output is correct |
26 |
Correct |
545 ms |
37880 KB |
Output is correct |
27 |
Correct |
645 ms |
48804 KB |
Output is correct |
28 |
Correct |
530 ms |
43524 KB |
Output is correct |
29 |
Correct |
619 ms |
44764 KB |
Output is correct |
30 |
Correct |
501 ms |
37156 KB |
Output is correct |
31 |
Correct |
621 ms |
48792 KB |
Output is correct |
32 |
Correct |
694 ms |
48944 KB |
Output is correct |
33 |
Correct |
649 ms |
45300 KB |
Output is correct |
34 |
Correct |
482 ms |
40260 KB |
Output is correct |
35 |
Correct |
601 ms |
49472 KB |
Output is correct |
36 |
Correct |
642 ms |
46044 KB |
Output is correct |
37 |
Correct |
688 ms |
49484 KB |
Output is correct |
38 |
Correct |
586 ms |
46052 KB |
Output is correct |
39 |
Correct |
677 ms |
49608 KB |
Output is correct |
40 |
Correct |
636 ms |
46000 KB |
Output is correct |
41 |
Correct |
608 ms |
49524 KB |
Output is correct |
42 |
Correct |
577 ms |
46000 KB |
Output is correct |
43 |
Correct |
545 ms |
41620 KB |
Output is correct |
44 |
Correct |
612 ms |
45264 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
565 ms |
39568 KB |
Output is correct |
2 |
Correct |
541 ms |
44244 KB |
Output is correct |
3 |
Correct |
585 ms |
25504 KB |
Output is correct |
4 |
Correct |
519 ms |
44140 KB |
Output is correct |
5 |
Correct |
515 ms |
44512 KB |
Output is correct |
6 |
Correct |
546 ms |
42192 KB |
Output is correct |
7 |
Correct |
590 ms |
40592 KB |
Output is correct |
8 |
Correct |
520 ms |
45088 KB |
Output is correct |
9 |
Correct |
575 ms |
43924 KB |
Output is correct |
10 |
Correct |
599 ms |
49540 KB |
Output is correct |
11 |
Correct |
587 ms |
45988 KB |
Output is correct |
12 |
Correct |
590 ms |
49428 KB |
Output is correct |
13 |
Correct |
562 ms |
45928 KB |
Output is correct |
14 |
Correct |
605 ms |
49544 KB |
Output is correct |
15 |
Correct |
533 ms |
45956 KB |
Output is correct |
16 |
Correct |
615 ms |
49540 KB |
Output is correct |
17 |
Correct |
625 ms |
46048 KB |
Output is correct |
18 |
Correct |
495 ms |
20512 KB |
Output is correct |
19 |
Runtime error |
1333 ms |
1048580 KB |
Execution killed with signal 9 |
20 |
Halted |
0 ms |
0 KB |
- |