# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
846809 |
2023-09-08T13:27:23 Z |
Abito |
Crossing (JOI21_crossing) |
C++17 |
|
1326 ms |
24376 KB |
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
#define y1 YONE
typedef unsigned long long ull;
using namespace std;
struct que{
int l,r;char x;
};
const int N=2e5+5;
int n,seg[4*N+5],q,po[N],pj[N],pi[N];
char a[N],b[N],lazy[4*N+5];
set<string> s;
que c[N];
bool ans[N];
string cross(string a,string b){
string c;
for (int i=0;i<a.size();i++){
if (a[i]==b[i]){
c+=a[i];continue;
}string v="JOI";
for (int j=0;j<3;j++){
if (v[j]==a[i] || v[j]==b[i]) continue;
c+=v[j];
}
}return c;
}
int build(int node,int l,int r){
lazy[node]='A';
if (l==r) return seg[node]=(a[l]==b[l]);
int mid=(l+r)/2;
return seg[node]=build(node*2,l,mid)+build(node*2+1,mid+1,r);
}
int edit(int node,int l,int r,int lx,int rx,char x){
if (r<lx || l>rx){
if (lazy[node]!='A'){
if (lazy[node]=='O') seg[node]=po[r]-po[l-1];
elif (lazy[node]=='J') seg[node]=pj[r]-pj[l-1];
else seg[node]=pi[r]-pi[l-1];
}return seg[node];
}
if (l>=lx && r<=rx){
lazy[node]=x;
if (lazy[node]=='O') seg[node]=po[r]-po[l-1];
elif (lazy[node]=='J') seg[node]=pj[r]-pj[l-1];
else seg[node]=pi[r]-pi[l-1];
return seg[node];
}int mid=(l+r)/2;
if (lazy[node]!='A'){
lazy[node*2]=lazy[node];
lazy[node*2+1]=lazy[node];
lazy[node]='A';
}return seg[node]=edit(node*2,l,mid,lx,rx,x)+edit(node*2+1,mid+1,r,lx,rx,x);
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin>>n;string h;cin>>h,s.ep(h),cin>>h,s.ep(h),cin>>h,s.ep(h);
while (true){
set<string> z;
for (auto u:s){
for (auto v:s){
z.ep(cross(u,v));
}
}bool ok=false;
for (auto u:z){
if (s.count(u)) continue;
ok=true;
s.ep(u);
}if (!ok) break;
}
cin>>q;
for (int i=1;i<=n;i++) cin>>b[i];
for (int i=1;i<=q;i++) cin>>c[i].l>>c[i].r>>c[i].x;
for (auto u:s){
for (int i=1;i<=n;i++){
a[i]=u[i-1];
po[i]=po[i-1],pj[i]=pj[i-1],pi[i]=pi[i-1];
if (a[i]=='J') pj[i]++;
elif (a[i]=='O') po[i]++;
else pi[i]++;
}
build(1,1,n);
if (seg[1]==n) ans[0]|=1;
for (int i=1;i<=q;i++){
edit(1,1,n,c[i].l,c[i].r,c[i].x);
if (seg[1]==n) ans[i]|=1;
}
}for (int i=0;i<=q;i++){
if (ans[i]) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
Compilation message
Main.cpp: In function 'std::string cross(std::string, std::string)':
Main.cpp:26:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for (int i=0;i<a.size();i++){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
9040 KB |
Output is correct |
2 |
Correct |
54 ms |
9040 KB |
Output is correct |
3 |
Correct |
68 ms |
9064 KB |
Output is correct |
4 |
Correct |
48 ms |
9300 KB |
Output is correct |
5 |
Correct |
46 ms |
9296 KB |
Output is correct |
6 |
Correct |
49 ms |
9228 KB |
Output is correct |
7 |
Correct |
51 ms |
9296 KB |
Output is correct |
8 |
Correct |
56 ms |
9300 KB |
Output is correct |
9 |
Correct |
53 ms |
9428 KB |
Output is correct |
10 |
Correct |
55 ms |
9156 KB |
Output is correct |
11 |
Correct |
52 ms |
9040 KB |
Output is correct |
12 |
Correct |
60 ms |
9196 KB |
Output is correct |
13 |
Correct |
58 ms |
9044 KB |
Output is correct |
14 |
Correct |
54 ms |
9188 KB |
Output is correct |
15 |
Correct |
50 ms |
9172 KB |
Output is correct |
16 |
Correct |
58 ms |
9176 KB |
Output is correct |
17 |
Correct |
56 ms |
9292 KB |
Output is correct |
18 |
Correct |
51 ms |
9296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
9040 KB |
Output is correct |
2 |
Correct |
54 ms |
9040 KB |
Output is correct |
3 |
Correct |
68 ms |
9064 KB |
Output is correct |
4 |
Correct |
48 ms |
9300 KB |
Output is correct |
5 |
Correct |
46 ms |
9296 KB |
Output is correct |
6 |
Correct |
49 ms |
9228 KB |
Output is correct |
7 |
Correct |
51 ms |
9296 KB |
Output is correct |
8 |
Correct |
56 ms |
9300 KB |
Output is correct |
9 |
Correct |
53 ms |
9428 KB |
Output is correct |
10 |
Correct |
55 ms |
9156 KB |
Output is correct |
11 |
Correct |
52 ms |
9040 KB |
Output is correct |
12 |
Correct |
60 ms |
9196 KB |
Output is correct |
13 |
Correct |
58 ms |
9044 KB |
Output is correct |
14 |
Correct |
54 ms |
9188 KB |
Output is correct |
15 |
Correct |
50 ms |
9172 KB |
Output is correct |
16 |
Correct |
58 ms |
9176 KB |
Output is correct |
17 |
Correct |
56 ms |
9292 KB |
Output is correct |
18 |
Correct |
51 ms |
9296 KB |
Output is correct |
19 |
Correct |
138 ms |
17968 KB |
Output is correct |
20 |
Correct |
143 ms |
17964 KB |
Output is correct |
21 |
Correct |
97 ms |
17664 KB |
Output is correct |
22 |
Correct |
114 ms |
17608 KB |
Output is correct |
23 |
Correct |
73 ms |
9468 KB |
Output is correct |
24 |
Correct |
81 ms |
9552 KB |
Output is correct |
25 |
Correct |
114 ms |
17968 KB |
Output is correct |
26 |
Correct |
124 ms |
17976 KB |
Output is correct |
27 |
Correct |
127 ms |
18024 KB |
Output is correct |
28 |
Correct |
127 ms |
18044 KB |
Output is correct |
29 |
Correct |
121 ms |
17900 KB |
Output is correct |
30 |
Correct |
90 ms |
9596 KB |
Output is correct |
31 |
Correct |
129 ms |
17972 KB |
Output is correct |
32 |
Correct |
125 ms |
17652 KB |
Output is correct |
33 |
Correct |
79 ms |
9460 KB |
Output is correct |
34 |
Correct |
140 ms |
17976 KB |
Output is correct |
35 |
Correct |
105 ms |
16776 KB |
Output is correct |
36 |
Correct |
86 ms |
9424 KB |
Output is correct |
37 |
Correct |
70 ms |
9504 KB |
Output is correct |
38 |
Correct |
137 ms |
18240 KB |
Output is correct |
39 |
Correct |
84 ms |
18220 KB |
Output is correct |
40 |
Correct |
96 ms |
14428 KB |
Output is correct |
41 |
Correct |
144 ms |
18292 KB |
Output is correct |
42 |
Correct |
40 ms |
18216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
9040 KB |
Output is correct |
2 |
Correct |
54 ms |
9040 KB |
Output is correct |
3 |
Correct |
68 ms |
9064 KB |
Output is correct |
4 |
Correct |
48 ms |
9300 KB |
Output is correct |
5 |
Correct |
46 ms |
9296 KB |
Output is correct |
6 |
Correct |
49 ms |
9228 KB |
Output is correct |
7 |
Correct |
51 ms |
9296 KB |
Output is correct |
8 |
Correct |
56 ms |
9300 KB |
Output is correct |
9 |
Correct |
53 ms |
9428 KB |
Output is correct |
10 |
Correct |
55 ms |
9156 KB |
Output is correct |
11 |
Correct |
52 ms |
9040 KB |
Output is correct |
12 |
Correct |
60 ms |
9196 KB |
Output is correct |
13 |
Correct |
58 ms |
9044 KB |
Output is correct |
14 |
Correct |
54 ms |
9188 KB |
Output is correct |
15 |
Correct |
50 ms |
9172 KB |
Output is correct |
16 |
Correct |
58 ms |
9176 KB |
Output is correct |
17 |
Correct |
56 ms |
9292 KB |
Output is correct |
18 |
Correct |
51 ms |
9296 KB |
Output is correct |
19 |
Correct |
279 ms |
9160 KB |
Output is correct |
20 |
Correct |
255 ms |
9180 KB |
Output is correct |
21 |
Correct |
102 ms |
9300 KB |
Output is correct |
22 |
Correct |
84 ms |
9300 KB |
Output is correct |
23 |
Correct |
122 ms |
9404 KB |
Output is correct |
24 |
Correct |
92 ms |
9344 KB |
Output is correct |
25 |
Correct |
104 ms |
9268 KB |
Output is correct |
26 |
Correct |
94 ms |
9344 KB |
Output is correct |
27 |
Correct |
94 ms |
9300 KB |
Output is correct |
28 |
Correct |
117 ms |
9356 KB |
Output is correct |
29 |
Correct |
100 ms |
9344 KB |
Output is correct |
30 |
Correct |
108 ms |
9300 KB |
Output is correct |
31 |
Correct |
233 ms |
9348 KB |
Output is correct |
32 |
Correct |
236 ms |
9340 KB |
Output is correct |
33 |
Correct |
253 ms |
9344 KB |
Output is correct |
34 |
Correct |
211 ms |
9348 KB |
Output is correct |
35 |
Correct |
247 ms |
9044 KB |
Output is correct |
36 |
Correct |
241 ms |
9300 KB |
Output is correct |
37 |
Correct |
241 ms |
9184 KB |
Output is correct |
38 |
Correct |
245 ms |
9184 KB |
Output is correct |
39 |
Correct |
243 ms |
9044 KB |
Output is correct |
40 |
Correct |
241 ms |
9168 KB |
Output is correct |
41 |
Correct |
248 ms |
9184 KB |
Output is correct |
42 |
Correct |
239 ms |
9176 KB |
Output is correct |
43 |
Correct |
239 ms |
9296 KB |
Output is correct |
44 |
Correct |
248 ms |
9416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
9040 KB |
Output is correct |
2 |
Correct |
54 ms |
9040 KB |
Output is correct |
3 |
Correct |
68 ms |
9064 KB |
Output is correct |
4 |
Correct |
48 ms |
9300 KB |
Output is correct |
5 |
Correct |
46 ms |
9296 KB |
Output is correct |
6 |
Correct |
49 ms |
9228 KB |
Output is correct |
7 |
Correct |
51 ms |
9296 KB |
Output is correct |
8 |
Correct |
56 ms |
9300 KB |
Output is correct |
9 |
Correct |
53 ms |
9428 KB |
Output is correct |
10 |
Correct |
55 ms |
9156 KB |
Output is correct |
11 |
Correct |
52 ms |
9040 KB |
Output is correct |
12 |
Correct |
60 ms |
9196 KB |
Output is correct |
13 |
Correct |
58 ms |
9044 KB |
Output is correct |
14 |
Correct |
54 ms |
9188 KB |
Output is correct |
15 |
Correct |
50 ms |
9172 KB |
Output is correct |
16 |
Correct |
58 ms |
9176 KB |
Output is correct |
17 |
Correct |
56 ms |
9292 KB |
Output is correct |
18 |
Correct |
51 ms |
9296 KB |
Output is correct |
19 |
Correct |
138 ms |
17968 KB |
Output is correct |
20 |
Correct |
143 ms |
17964 KB |
Output is correct |
21 |
Correct |
97 ms |
17664 KB |
Output is correct |
22 |
Correct |
114 ms |
17608 KB |
Output is correct |
23 |
Correct |
73 ms |
9468 KB |
Output is correct |
24 |
Correct |
81 ms |
9552 KB |
Output is correct |
25 |
Correct |
114 ms |
17968 KB |
Output is correct |
26 |
Correct |
124 ms |
17976 KB |
Output is correct |
27 |
Correct |
127 ms |
18024 KB |
Output is correct |
28 |
Correct |
127 ms |
18044 KB |
Output is correct |
29 |
Correct |
121 ms |
17900 KB |
Output is correct |
30 |
Correct |
90 ms |
9596 KB |
Output is correct |
31 |
Correct |
129 ms |
17972 KB |
Output is correct |
32 |
Correct |
125 ms |
17652 KB |
Output is correct |
33 |
Correct |
79 ms |
9460 KB |
Output is correct |
34 |
Correct |
140 ms |
17976 KB |
Output is correct |
35 |
Correct |
105 ms |
16776 KB |
Output is correct |
36 |
Correct |
86 ms |
9424 KB |
Output is correct |
37 |
Correct |
70 ms |
9504 KB |
Output is correct |
38 |
Correct |
137 ms |
18240 KB |
Output is correct |
39 |
Correct |
84 ms |
18220 KB |
Output is correct |
40 |
Correct |
96 ms |
14428 KB |
Output is correct |
41 |
Correct |
144 ms |
18292 KB |
Output is correct |
42 |
Correct |
40 ms |
18216 KB |
Output is correct |
43 |
Correct |
279 ms |
9160 KB |
Output is correct |
44 |
Correct |
255 ms |
9180 KB |
Output is correct |
45 |
Correct |
102 ms |
9300 KB |
Output is correct |
46 |
Correct |
84 ms |
9300 KB |
Output is correct |
47 |
Correct |
122 ms |
9404 KB |
Output is correct |
48 |
Correct |
92 ms |
9344 KB |
Output is correct |
49 |
Correct |
104 ms |
9268 KB |
Output is correct |
50 |
Correct |
94 ms |
9344 KB |
Output is correct |
51 |
Correct |
94 ms |
9300 KB |
Output is correct |
52 |
Correct |
117 ms |
9356 KB |
Output is correct |
53 |
Correct |
100 ms |
9344 KB |
Output is correct |
54 |
Correct |
108 ms |
9300 KB |
Output is correct |
55 |
Correct |
233 ms |
9348 KB |
Output is correct |
56 |
Correct |
236 ms |
9340 KB |
Output is correct |
57 |
Correct |
253 ms |
9344 KB |
Output is correct |
58 |
Correct |
211 ms |
9348 KB |
Output is correct |
59 |
Correct |
247 ms |
9044 KB |
Output is correct |
60 |
Correct |
241 ms |
9300 KB |
Output is correct |
61 |
Correct |
241 ms |
9184 KB |
Output is correct |
62 |
Correct |
245 ms |
9184 KB |
Output is correct |
63 |
Correct |
243 ms |
9044 KB |
Output is correct |
64 |
Correct |
241 ms |
9168 KB |
Output is correct |
65 |
Correct |
248 ms |
9184 KB |
Output is correct |
66 |
Correct |
239 ms |
9176 KB |
Output is correct |
67 |
Correct |
239 ms |
9296 KB |
Output is correct |
68 |
Correct |
248 ms |
9416 KB |
Output is correct |
69 |
Correct |
1199 ms |
22576 KB |
Output is correct |
70 |
Correct |
1326 ms |
23856 KB |
Output is correct |
71 |
Correct |
168 ms |
12124 KB |
Output is correct |
72 |
Correct |
163 ms |
11904 KB |
Output is correct |
73 |
Correct |
181 ms |
11980 KB |
Output is correct |
74 |
Correct |
265 ms |
21492 KB |
Output is correct |
75 |
Correct |
188 ms |
12004 KB |
Output is correct |
76 |
Correct |
297 ms |
22776 KB |
Output is correct |
77 |
Correct |
272 ms |
21724 KB |
Output is correct |
78 |
Correct |
174 ms |
11992 KB |
Output is correct |
79 |
Correct |
167 ms |
11864 KB |
Output is correct |
80 |
Correct |
871 ms |
21632 KB |
Output is correct |
81 |
Correct |
443 ms |
11924 KB |
Output is correct |
82 |
Correct |
1129 ms |
23952 KB |
Output is correct |
83 |
Correct |
1026 ms |
23436 KB |
Output is correct |
84 |
Correct |
467 ms |
11984 KB |
Output is correct |
85 |
Correct |
434 ms |
12084 KB |
Output is correct |
86 |
Correct |
825 ms |
22020 KB |
Output is correct |
87 |
Correct |
916 ms |
24256 KB |
Output is correct |
88 |
Correct |
464 ms |
11984 KB |
Output is correct |
89 |
Correct |
791 ms |
22968 KB |
Output is correct |
90 |
Correct |
918 ms |
23972 KB |
Output is correct |
91 |
Correct |
477 ms |
12028 KB |
Output is correct |
92 |
Correct |
817 ms |
21980 KB |
Output is correct |
93 |
Correct |
424 ms |
11828 KB |
Output is correct |
94 |
Correct |
428 ms |
11952 KB |
Output is correct |
95 |
Correct |
431 ms |
12024 KB |
Output is correct |
96 |
Correct |
108 ms |
21656 KB |
Output is correct |
97 |
Correct |
498 ms |
24164 KB |
Output is correct |
98 |
Correct |
789 ms |
19312 KB |
Output is correct |
99 |
Correct |
1227 ms |
24376 KB |
Output is correct |
100 |
Correct |
398 ms |
23548 KB |
Output is correct |