# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
600411 |
2022-07-20T20:19:49 Z |
Plurm |
Crossing (JOI21_crossing) |
C++11 |
|
621 ms |
12684 KB |
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int B = 53;
const int invB = 788461544;
int bp[1 << 18];
string s, t;
int templ;
void prep(){
for(char c : s){
templ = 1ll * templ * B % MOD;
templ += c;
templ %= MOD;
}
}
int seg[1 << 19];
int lb[1 << 19];
int rb[1 << 19];
char lazy[1 << 19];
void build(int c, int l, int r){
lb[c] = l;
rb[c] = r;
if(l == r){
seg[c] = t[l];
return;
}
int k = (l + r)/2;
build(2*c, l, k);
build(2*c+1, k+1, r);
seg[c] = (1ll * seg[2*c] * bp[r-k] % MOD + seg[2*c+1] % MOD) % MOD;
}
void prop(int c){
if(lazy[c]){
seg[c] = 1ll * lazy[c] * ((bp[rb[c] - lb[c] + 1] + MOD - 1) % MOD) % MOD * invB % MOD;
if(lb[c] != rb[c]){
lazy[2*c] = lazy[c];
lazy[2*c+1] = lazy[c];
}
lazy[c] = '\0';
}
}
void update(int c, int l, int r, char x){
if(lb[c] == l && rb[c] == r) lazy[c] = x;
prop(c);
if(lb[c] == l && rb[c] == r) return;
int k = (lb[c] + rb[c]) /2;
if(l <= k && k < r){
update(2*c, l, k, x);
update(2*c+1, k+1, r, x);
}else if(r <= k){
update(2*c, l, r, x);
prop(2*c+1);
}else{
prop(2*c);
update(2*c+1, l, r, x);
}
seg[c] = (1ll * seg[2*c] * bp[rb[c]-k] % MOD + seg[2*c+1] % MOD) % MOD;
}
bool check(){
prop(1);
return seg[1] == templ;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n >> s >> s >> s;
bp[0] = 1;
for(int i = 1; i <= n; i++){
bp[i] = 1ll * bp[i-1] * B % MOD;
}
prep();
int q;
cin >> q;
cin >> t;
build(1, 0, n-1);
cout << (check() ? "Yes" : "No") << endl;
while(q--){
int l, r;
char c;
cin >> l >> r >> c;
update(1, l-1, r-1, c);
cout << (check() ? "Yes" : "No") << endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
319 ms |
812 KB |
Output is correct |
2 |
Correct |
323 ms |
932 KB |
Output is correct |
3 |
Correct |
350 ms |
908 KB |
Output is correct |
4 |
Correct |
292 ms |
836 KB |
Output is correct |
5 |
Correct |
302 ms |
824 KB |
Output is correct |
6 |
Correct |
285 ms |
984 KB |
Output is correct |
7 |
Correct |
291 ms |
924 KB |
Output is correct |
8 |
Correct |
328 ms |
892 KB |
Output is correct |
9 |
Correct |
290 ms |
904 KB |
Output is correct |
10 |
Correct |
363 ms |
824 KB |
Output is correct |
11 |
Correct |
315 ms |
924 KB |
Output is correct |
12 |
Correct |
364 ms |
920 KB |
Output is correct |
13 |
Correct |
307 ms |
924 KB |
Output is correct |
14 |
Correct |
309 ms |
840 KB |
Output is correct |
15 |
Correct |
294 ms |
936 KB |
Output is correct |
16 |
Correct |
296 ms |
924 KB |
Output is correct |
17 |
Correct |
294 ms |
1028 KB |
Output is correct |
18 |
Correct |
305 ms |
948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
319 ms |
812 KB |
Output is correct |
2 |
Correct |
323 ms |
932 KB |
Output is correct |
3 |
Correct |
350 ms |
908 KB |
Output is correct |
4 |
Correct |
292 ms |
836 KB |
Output is correct |
5 |
Correct |
302 ms |
824 KB |
Output is correct |
6 |
Correct |
285 ms |
984 KB |
Output is correct |
7 |
Correct |
291 ms |
924 KB |
Output is correct |
8 |
Correct |
328 ms |
892 KB |
Output is correct |
9 |
Correct |
290 ms |
904 KB |
Output is correct |
10 |
Correct |
363 ms |
824 KB |
Output is correct |
11 |
Correct |
315 ms |
924 KB |
Output is correct |
12 |
Correct |
364 ms |
920 KB |
Output is correct |
13 |
Correct |
307 ms |
924 KB |
Output is correct |
14 |
Correct |
309 ms |
840 KB |
Output is correct |
15 |
Correct |
294 ms |
936 KB |
Output is correct |
16 |
Correct |
296 ms |
924 KB |
Output is correct |
17 |
Correct |
294 ms |
1028 KB |
Output is correct |
18 |
Correct |
305 ms |
948 KB |
Output is correct |
19 |
Correct |
581 ms |
9920 KB |
Output is correct |
20 |
Correct |
621 ms |
12108 KB |
Output is correct |
21 |
Correct |
402 ms |
12168 KB |
Output is correct |
22 |
Correct |
420 ms |
11960 KB |
Output is correct |
23 |
Correct |
379 ms |
3800 KB |
Output is correct |
24 |
Correct |
341 ms |
3756 KB |
Output is correct |
25 |
Correct |
437 ms |
12568 KB |
Output is correct |
26 |
Correct |
448 ms |
12568 KB |
Output is correct |
27 |
Correct |
491 ms |
12512 KB |
Output is correct |
28 |
Correct |
468 ms |
12504 KB |
Output is correct |
29 |
Correct |
484 ms |
12452 KB |
Output is correct |
30 |
Correct |
432 ms |
3772 KB |
Output is correct |
31 |
Correct |
484 ms |
12532 KB |
Output is correct |
32 |
Correct |
455 ms |
12256 KB |
Output is correct |
33 |
Correct |
347 ms |
3740 KB |
Output is correct |
34 |
Correct |
474 ms |
12536 KB |
Output is correct |
35 |
Correct |
402 ms |
11800 KB |
Output is correct |
36 |
Correct |
396 ms |
3744 KB |
Output is correct |
37 |
Correct |
349 ms |
3764 KB |
Output is correct |
38 |
Correct |
508 ms |
11988 KB |
Output is correct |
39 |
Correct |
381 ms |
12272 KB |
Output is correct |
40 |
Correct |
402 ms |
8596 KB |
Output is correct |
41 |
Correct |
606 ms |
12684 KB |
Output is correct |
42 |
Correct |
282 ms |
11456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
319 ms |
812 KB |
Output is correct |
2 |
Correct |
323 ms |
932 KB |
Output is correct |
3 |
Correct |
350 ms |
908 KB |
Output is correct |
4 |
Correct |
292 ms |
836 KB |
Output is correct |
5 |
Correct |
302 ms |
824 KB |
Output is correct |
6 |
Correct |
285 ms |
984 KB |
Output is correct |
7 |
Correct |
291 ms |
924 KB |
Output is correct |
8 |
Correct |
328 ms |
892 KB |
Output is correct |
9 |
Correct |
290 ms |
904 KB |
Output is correct |
10 |
Correct |
363 ms |
824 KB |
Output is correct |
11 |
Correct |
315 ms |
924 KB |
Output is correct |
12 |
Correct |
364 ms |
920 KB |
Output is correct |
13 |
Correct |
307 ms |
924 KB |
Output is correct |
14 |
Correct |
309 ms |
840 KB |
Output is correct |
15 |
Correct |
294 ms |
936 KB |
Output is correct |
16 |
Correct |
296 ms |
924 KB |
Output is correct |
17 |
Correct |
294 ms |
1028 KB |
Output is correct |
18 |
Correct |
305 ms |
948 KB |
Output is correct |
19 |
Correct |
322 ms |
876 KB |
Output is correct |
20 |
Correct |
314 ms |
864 KB |
Output is correct |
21 |
Incorrect |
305 ms |
876 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
319 ms |
812 KB |
Output is correct |
2 |
Correct |
323 ms |
932 KB |
Output is correct |
3 |
Correct |
350 ms |
908 KB |
Output is correct |
4 |
Correct |
292 ms |
836 KB |
Output is correct |
5 |
Correct |
302 ms |
824 KB |
Output is correct |
6 |
Correct |
285 ms |
984 KB |
Output is correct |
7 |
Correct |
291 ms |
924 KB |
Output is correct |
8 |
Correct |
328 ms |
892 KB |
Output is correct |
9 |
Correct |
290 ms |
904 KB |
Output is correct |
10 |
Correct |
363 ms |
824 KB |
Output is correct |
11 |
Correct |
315 ms |
924 KB |
Output is correct |
12 |
Correct |
364 ms |
920 KB |
Output is correct |
13 |
Correct |
307 ms |
924 KB |
Output is correct |
14 |
Correct |
309 ms |
840 KB |
Output is correct |
15 |
Correct |
294 ms |
936 KB |
Output is correct |
16 |
Correct |
296 ms |
924 KB |
Output is correct |
17 |
Correct |
294 ms |
1028 KB |
Output is correct |
18 |
Correct |
305 ms |
948 KB |
Output is correct |
19 |
Correct |
581 ms |
9920 KB |
Output is correct |
20 |
Correct |
621 ms |
12108 KB |
Output is correct |
21 |
Correct |
402 ms |
12168 KB |
Output is correct |
22 |
Correct |
420 ms |
11960 KB |
Output is correct |
23 |
Correct |
379 ms |
3800 KB |
Output is correct |
24 |
Correct |
341 ms |
3756 KB |
Output is correct |
25 |
Correct |
437 ms |
12568 KB |
Output is correct |
26 |
Correct |
448 ms |
12568 KB |
Output is correct |
27 |
Correct |
491 ms |
12512 KB |
Output is correct |
28 |
Correct |
468 ms |
12504 KB |
Output is correct |
29 |
Correct |
484 ms |
12452 KB |
Output is correct |
30 |
Correct |
432 ms |
3772 KB |
Output is correct |
31 |
Correct |
484 ms |
12532 KB |
Output is correct |
32 |
Correct |
455 ms |
12256 KB |
Output is correct |
33 |
Correct |
347 ms |
3740 KB |
Output is correct |
34 |
Correct |
474 ms |
12536 KB |
Output is correct |
35 |
Correct |
402 ms |
11800 KB |
Output is correct |
36 |
Correct |
396 ms |
3744 KB |
Output is correct |
37 |
Correct |
349 ms |
3764 KB |
Output is correct |
38 |
Correct |
508 ms |
11988 KB |
Output is correct |
39 |
Correct |
381 ms |
12272 KB |
Output is correct |
40 |
Correct |
402 ms |
8596 KB |
Output is correct |
41 |
Correct |
606 ms |
12684 KB |
Output is correct |
42 |
Correct |
282 ms |
11456 KB |
Output is correct |
43 |
Correct |
322 ms |
876 KB |
Output is correct |
44 |
Correct |
314 ms |
864 KB |
Output is correct |
45 |
Incorrect |
305 ms |
876 KB |
Output isn't correct |
46 |
Halted |
0 ms |
0 KB |
- |