#include <bits/stdc++.h>
using namespace std;
int conv(char c){
if(c == 'I') return 0;
if(c == 'J') return 1;
return 2;
}
struct segTree{
struct node{
vector<int> cnt, real_cnt;
node(){
cnt.resize(3);
real_cnt.resize(3);
}
int wrong = 0, set_to = -1, all = 0;
};
vector<node> t;
int maxN = (1<<18);
segTree(string& real, string& fake){
t.resize(2*maxN);
for(int i = 0; i < real.size(); i++){
t[i+maxN].cnt[conv(fake[i])] = 1, t[i+maxN].real_cnt[conv(real[i])] = 1;
t[i+maxN].wrong = fake[i] != real[i];
t[i+maxN].all = 1;
}
build(1, 0, maxN);
}
void build(int v, int l, int r){
if(r-l == 1) return;
build(2*v, l, (l+r)/2), build(2*v+1, (l+r)/2, r);
t[v].all = t[v*2].all + t[v*2+1].all;
t[v].wrong = t[v*2].wrong + t[v*2+1].wrong;
for(int i = 0; i < 3; i++)
t[v].cnt[i] = t[v*2].cnt[i]+t[v*2+1].cnt[i];
for(int i = 0; i < 3; i++)
t[v].real_cnt[i] = t[v*2].real_cnt[i]+t[v*2+1].real_cnt[i];
}
void add(int v, int c){
t[v].cnt = {0,0,0};
t[v].cnt[c] = t[v].all;
t[v].wrong = t[v].all - t[v].real_cnt[c];
t[v].set_to = c;
}
void push(int v){
if(t[v].set_to == -1) return;
add(2*v, t[v].set_to), add(2*v+1, t[v].set_to);
t[v].set_to = -1;
}
void upd(int l, int r, int c){
upd(1, l, r, 0, maxN, c);
}
void upd(int v, int ll, int rr, int l, int r, int c){
if(min(r,rr) <= max(l,ll)) return;
if(ll <= l && r <= rr){
add(v, c);
return;
}
push(v);
upd(2*v, ll, rr, l, (l+r)/2, c), upd(2*v+1, ll, rr, (l+r)/2, r, c);
t[v].wrong = 0;
for(int i = 0; i < 3; i++)
t[v].cnt[i] = t[v*2].cnt[i]+t[v*2+1].cnt[i];
t[v].wrong = t[v*2].wrong + t[v*2+1].wrong;
}
};
char cross(char c1, char c2){
if(c2 < c1) swap(c1, c2);
if(c1 == c2) return c1;
if(c1 == 'I' && c2 == 'O') return 'J';
if(c1 == 'I' && c2 == 'J') return 'O';
return 'I';
}
int main(){
int n;
cin>>n;
set<string> v;
for(int i = 0; i < 3; i++){
string s;
cin>>s;
v.insert(s);
}
while(true){
bool added = false;
for(auto it = v.begin(); it != v.end(); it++)
for(auto it2 = v.begin(); it2 != it; it2++){
string s1 = *it, s2 = *it2;
string s = "";
for(int k = 0; k < n; k++)
s += cross(s1[k], s2[k]);
if(v.count(s) == 0){
added = true;
v.insert(s);
}
}
if(!added) break;
}
int q;
string fake;
cin>>q>>fake;
vector<segTree> trees;
for(auto it = v.begin(); it != v.end(); it++){
string s = *it;
trees.push_back(segTree(s, fake));
}
bool any = false;
for(int i = 0; i < trees.size(); i++)
any |= trees[i].t[1].wrong == 0;
cout << (any ? "Yes" : "No") << "\n";
while(q--){
int a, b;
char c;
cin>>a>>b>>c;
bool any = false;
for(int i = 0; i < trees.size(); i++){
trees[i].upd(a-1, b, conv(c));
any |= trees[i].t[1].wrong == 0;
}
cout << (any ? "Yes" : "No") << "\n";
}
}
Compilation message
Main.cpp: In constructor 'segTree::segTree(std::string&, std::string&)':
Main.cpp:22:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i = 0; i < real.size(); i++){
| ~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segTree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int i = 0; i < trees.size(); i++)
| ~~^~~~~~~~~~~~~~
Main.cpp:119:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segTree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int i = 0; i < trees.size(); i++){
| ~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
421 ms |
67844 KB |
Output is correct |
2 |
Correct |
453 ms |
68200 KB |
Output is correct |
3 |
Correct |
501 ms |
67900 KB |
Output is correct |
4 |
Correct |
467 ms |
68152 KB |
Output is correct |
5 |
Correct |
436 ms |
67924 KB |
Output is correct |
6 |
Correct |
413 ms |
68056 KB |
Output is correct |
7 |
Correct |
456 ms |
68108 KB |
Output is correct |
8 |
Correct |
416 ms |
68176 KB |
Output is correct |
9 |
Correct |
430 ms |
68324 KB |
Output is correct |
10 |
Correct |
420 ms |
68056 KB |
Output is correct |
11 |
Correct |
431 ms |
68124 KB |
Output is correct |
12 |
Correct |
416 ms |
68268 KB |
Output is correct |
13 |
Correct |
459 ms |
68168 KB |
Output is correct |
14 |
Correct |
430 ms |
68200 KB |
Output is correct |
15 |
Correct |
418 ms |
68180 KB |
Output is correct |
16 |
Correct |
417 ms |
67984 KB |
Output is correct |
17 |
Correct |
416 ms |
68000 KB |
Output is correct |
18 |
Correct |
430 ms |
67924 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
421 ms |
67844 KB |
Output is correct |
2 |
Correct |
453 ms |
68200 KB |
Output is correct |
3 |
Correct |
501 ms |
67900 KB |
Output is correct |
4 |
Correct |
467 ms |
68152 KB |
Output is correct |
5 |
Correct |
436 ms |
67924 KB |
Output is correct |
6 |
Correct |
413 ms |
68056 KB |
Output is correct |
7 |
Correct |
456 ms |
68108 KB |
Output is correct |
8 |
Correct |
416 ms |
68176 KB |
Output is correct |
9 |
Correct |
430 ms |
68324 KB |
Output is correct |
10 |
Correct |
420 ms |
68056 KB |
Output is correct |
11 |
Correct |
431 ms |
68124 KB |
Output is correct |
12 |
Correct |
416 ms |
68268 KB |
Output is correct |
13 |
Correct |
459 ms |
68168 KB |
Output is correct |
14 |
Correct |
430 ms |
68200 KB |
Output is correct |
15 |
Correct |
418 ms |
68180 KB |
Output is correct |
16 |
Correct |
417 ms |
67984 KB |
Output is correct |
17 |
Correct |
416 ms |
68000 KB |
Output is correct |
18 |
Correct |
430 ms |
67924 KB |
Output is correct |
19 |
Correct |
837 ms |
70832 KB |
Output is correct |
20 |
Correct |
668 ms |
70968 KB |
Output is correct |
21 |
Correct |
610 ms |
70548 KB |
Output is correct |
22 |
Correct |
626 ms |
70936 KB |
Output is correct |
23 |
Correct |
449 ms |
68944 KB |
Output is correct |
24 |
Correct |
466 ms |
68944 KB |
Output is correct |
25 |
Correct |
630 ms |
71020 KB |
Output is correct |
26 |
Correct |
657 ms |
70844 KB |
Output is correct |
27 |
Correct |
610 ms |
70828 KB |
Output is correct |
28 |
Correct |
789 ms |
70816 KB |
Output is correct |
29 |
Correct |
642 ms |
70728 KB |
Output is correct |
30 |
Correct |
514 ms |
68968 KB |
Output is correct |
31 |
Correct |
618 ms |
71044 KB |
Output is correct |
32 |
Correct |
668 ms |
70696 KB |
Output is correct |
33 |
Correct |
476 ms |
68972 KB |
Output is correct |
34 |
Correct |
702 ms |
70836 KB |
Output is correct |
35 |
Correct |
641 ms |
70380 KB |
Output is correct |
36 |
Correct |
456 ms |
68948 KB |
Output is correct |
37 |
Correct |
460 ms |
69036 KB |
Output is correct |
38 |
Correct |
646 ms |
70788 KB |
Output is correct |
39 |
Correct |
467 ms |
70872 KB |
Output is correct |
40 |
Correct |
651 ms |
70304 KB |
Output is correct |
41 |
Correct |
948 ms |
71108 KB |
Output is correct |
42 |
Correct |
426 ms |
70556 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
421 ms |
67844 KB |
Output is correct |
2 |
Correct |
453 ms |
68200 KB |
Output is correct |
3 |
Correct |
501 ms |
67900 KB |
Output is correct |
4 |
Correct |
467 ms |
68152 KB |
Output is correct |
5 |
Correct |
436 ms |
67924 KB |
Output is correct |
6 |
Correct |
413 ms |
68056 KB |
Output is correct |
7 |
Correct |
456 ms |
68108 KB |
Output is correct |
8 |
Correct |
416 ms |
68176 KB |
Output is correct |
9 |
Correct |
430 ms |
68324 KB |
Output is correct |
10 |
Correct |
420 ms |
68056 KB |
Output is correct |
11 |
Correct |
431 ms |
68124 KB |
Output is correct |
12 |
Correct |
416 ms |
68268 KB |
Output is correct |
13 |
Correct |
459 ms |
68168 KB |
Output is correct |
14 |
Correct |
430 ms |
68200 KB |
Output is correct |
15 |
Correct |
418 ms |
68180 KB |
Output is correct |
16 |
Correct |
417 ms |
67984 KB |
Output is correct |
17 |
Correct |
416 ms |
68000 KB |
Output is correct |
18 |
Correct |
430 ms |
67924 KB |
Output is correct |
19 |
Correct |
1680 ms |
593692 KB |
Output is correct |
20 |
Correct |
1904 ms |
593392 KB |
Output is correct |
21 |
Correct |
696 ms |
199508 KB |
Output is correct |
22 |
Correct |
662 ms |
199508 KB |
Output is correct |
23 |
Correct |
681 ms |
199500 KB |
Output is correct |
24 |
Correct |
685 ms |
199248 KB |
Output is correct |
25 |
Correct |
708 ms |
199616 KB |
Output is correct |
26 |
Correct |
667 ms |
199524 KB |
Output is correct |
27 |
Correct |
690 ms |
199696 KB |
Output is correct |
28 |
Correct |
642 ms |
199312 KB |
Output is correct |
29 |
Correct |
699 ms |
199764 KB |
Output is correct |
30 |
Correct |
645 ms |
199252 KB |
Output is correct |
31 |
Correct |
1674 ms |
593488 KB |
Output is correct |
32 |
Correct |
1643 ms |
593692 KB |
Output is correct |
33 |
Correct |
1617 ms |
594024 KB |
Output is correct |
34 |
Correct |
1600 ms |
593232 KB |
Output is correct |
35 |
Correct |
1591 ms |
593744 KB |
Output is correct |
36 |
Correct |
1633 ms |
593580 KB |
Output is correct |
37 |
Correct |
1574 ms |
593744 KB |
Output is correct |
38 |
Correct |
1652 ms |
593832 KB |
Output is correct |
39 |
Correct |
1658 ms |
593324 KB |
Output is correct |
40 |
Correct |
1643 ms |
593676 KB |
Output is correct |
41 |
Correct |
1658 ms |
593656 KB |
Output is correct |
42 |
Correct |
1666 ms |
593704 KB |
Output is correct |
43 |
Correct |
1628 ms |
594020 KB |
Output is correct |
44 |
Correct |
1585 ms |
593544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
421 ms |
67844 KB |
Output is correct |
2 |
Correct |
453 ms |
68200 KB |
Output is correct |
3 |
Correct |
501 ms |
67900 KB |
Output is correct |
4 |
Correct |
467 ms |
68152 KB |
Output is correct |
5 |
Correct |
436 ms |
67924 KB |
Output is correct |
6 |
Correct |
413 ms |
68056 KB |
Output is correct |
7 |
Correct |
456 ms |
68108 KB |
Output is correct |
8 |
Correct |
416 ms |
68176 KB |
Output is correct |
9 |
Correct |
430 ms |
68324 KB |
Output is correct |
10 |
Correct |
420 ms |
68056 KB |
Output is correct |
11 |
Correct |
431 ms |
68124 KB |
Output is correct |
12 |
Correct |
416 ms |
68268 KB |
Output is correct |
13 |
Correct |
459 ms |
68168 KB |
Output is correct |
14 |
Correct |
430 ms |
68200 KB |
Output is correct |
15 |
Correct |
418 ms |
68180 KB |
Output is correct |
16 |
Correct |
417 ms |
67984 KB |
Output is correct |
17 |
Correct |
416 ms |
68000 KB |
Output is correct |
18 |
Correct |
430 ms |
67924 KB |
Output is correct |
19 |
Correct |
837 ms |
70832 KB |
Output is correct |
20 |
Correct |
668 ms |
70968 KB |
Output is correct |
21 |
Correct |
610 ms |
70548 KB |
Output is correct |
22 |
Correct |
626 ms |
70936 KB |
Output is correct |
23 |
Correct |
449 ms |
68944 KB |
Output is correct |
24 |
Correct |
466 ms |
68944 KB |
Output is correct |
25 |
Correct |
630 ms |
71020 KB |
Output is correct |
26 |
Correct |
657 ms |
70844 KB |
Output is correct |
27 |
Correct |
610 ms |
70828 KB |
Output is correct |
28 |
Correct |
789 ms |
70816 KB |
Output is correct |
29 |
Correct |
642 ms |
70728 KB |
Output is correct |
30 |
Correct |
514 ms |
68968 KB |
Output is correct |
31 |
Correct |
618 ms |
71044 KB |
Output is correct |
32 |
Correct |
668 ms |
70696 KB |
Output is correct |
33 |
Correct |
476 ms |
68972 KB |
Output is correct |
34 |
Correct |
702 ms |
70836 KB |
Output is correct |
35 |
Correct |
641 ms |
70380 KB |
Output is correct |
36 |
Correct |
456 ms |
68948 KB |
Output is correct |
37 |
Correct |
460 ms |
69036 KB |
Output is correct |
38 |
Correct |
646 ms |
70788 KB |
Output is correct |
39 |
Correct |
467 ms |
70872 KB |
Output is correct |
40 |
Correct |
651 ms |
70304 KB |
Output is correct |
41 |
Correct |
948 ms |
71108 KB |
Output is correct |
42 |
Correct |
426 ms |
70556 KB |
Output is correct |
43 |
Correct |
1680 ms |
593692 KB |
Output is correct |
44 |
Correct |
1904 ms |
593392 KB |
Output is correct |
45 |
Correct |
696 ms |
199508 KB |
Output is correct |
46 |
Correct |
662 ms |
199508 KB |
Output is correct |
47 |
Correct |
681 ms |
199500 KB |
Output is correct |
48 |
Correct |
685 ms |
199248 KB |
Output is correct |
49 |
Correct |
708 ms |
199616 KB |
Output is correct |
50 |
Correct |
667 ms |
199524 KB |
Output is correct |
51 |
Correct |
690 ms |
199696 KB |
Output is correct |
52 |
Correct |
642 ms |
199312 KB |
Output is correct |
53 |
Correct |
699 ms |
199764 KB |
Output is correct |
54 |
Correct |
645 ms |
199252 KB |
Output is correct |
55 |
Correct |
1674 ms |
593488 KB |
Output is correct |
56 |
Correct |
1643 ms |
593692 KB |
Output is correct |
57 |
Correct |
1617 ms |
594024 KB |
Output is correct |
58 |
Correct |
1600 ms |
593232 KB |
Output is correct |
59 |
Correct |
1591 ms |
593744 KB |
Output is correct |
60 |
Correct |
1633 ms |
593580 KB |
Output is correct |
61 |
Correct |
1574 ms |
593744 KB |
Output is correct |
62 |
Correct |
1652 ms |
593832 KB |
Output is correct |
63 |
Correct |
1658 ms |
593324 KB |
Output is correct |
64 |
Correct |
1643 ms |
593676 KB |
Output is correct |
65 |
Correct |
1658 ms |
593656 KB |
Output is correct |
66 |
Correct |
1666 ms |
593704 KB |
Output is correct |
67 |
Correct |
1628 ms |
594020 KB |
Output is correct |
68 |
Correct |
1585 ms |
593544 KB |
Output is correct |
69 |
Execution timed out |
7061 ms |
597116 KB |
Time limit exceeded |
70 |
Halted |
0 ms |
0 KB |
- |