oj.uz

Submission #420228

# Submission time Handle Problem Language Result Execution time Memory
420228 2021-06-08T07:56:45 Z parsabahrami Crossing (JOI21_crossing) C++17
100 / 100
 895 ms 10588 KB 
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second
#define lc                          id << 1
#define rc                          lc | 1

const int N = 2e5 + 10, MOD = 1e9 + 7;
int seg[N << 2], lz[N << 2], pw[N], ps[N], base = 31, n, q; char S[N], T[N]; string C[3];  
set<string> st;

string sum(string a, string b) {
    string ret = a;
    for (int i = 0; i < SZ(a); i++) 
        if (a[i] == b[i]) ret[i] = a[i];
        else ret[i] = 'J' ^ 'O' ^ 'I' ^ a[i] ^ b[i];
    return ret;
}

void bld(int id = 1, int l = 1, int r = n + 1) {
    if (r - l < 2) {
        seg[id] = T[l] - 'A' + 1;
        //printf("%d %d %d\n", l, r, seg[id]);
        return;
    }
    int md = (l + r) >> 1;
    bld(lc, l, md);
    bld(rc, md, r);
    seg[id] = (seg[lc] * 1ll * pw[r - md] % MOD + seg[rc]) % MOD;
    //printf("%d %d %d\n", l, r, seg[id]);
}

void shift(int id, int l, int r) {
    if (!lz[id]) return;
    seg[id] = 1ll * lz[id] * (ps[r - l - 1] % MOD) % MOD;
    if (r - l > 1) 
        lz[lc] = lz[id], lz[rc] = lz[id];
    lz[id] = 0;
}

void upd(int ql, int qr, char c, int id = 1, int l = 1, int r = n + 1) {
    shift(id, l, r);
    if (qr <= l || r <= ql) return;
    if (ql <= l && r <= qr) {
        lz[id] = c - 'A' + 1;
        return shift(id, l, r);
    }
    int md = (l + r) >> 1;
    upd(ql, qr, c, lc, l, md);
    upd(ql, qr, c, rc, md, r);
    seg[id] = (seg[lc] * 1ll * pw[r - md] % MOD + seg[rc]) % MOD;
}

int main() {
    pw[0] = ps[0] = 1;
    for (int i = 1; i < N; i++) {
        pw[i] = 1ll * pw[i - 1] * base % MOD;
        ps[i] = (ps[i - 1] + pw[i]) % MOD;
    }
  scanf("%d", &n);
    for (int i : {0, 1, 2}) 
        scanf("%s", S + 1), C[i] = S + 1;
    st.insert(C[0]), st.insert(C[2]), st.insert(C[1]);
    for (int i = 1; i <= 100; i++) {
        int prev = SZ(st);
        for (string s1 : st) 
            for (string s2 : st) 
                st.insert(sum(s1, s2));
        if (SZ(st) == prev) break;
    }
    set<int> mp;
    for (string s : st) {
        int h = 0;
        for (char c : s) {
            h = (1ll * h * base % MOD + (c - 'A' + 1)) % MOD;
        }
        mp.insert(h);
    }
    scanf("%d%s", &q, T + 1);
    bld();
    printf(mp.find(seg[1]) != mp.end() ? "Yes\n" : "No\n");
    for (int i = 1; i <= q; i++) {
        int l, r; char c; cin >> l >> r >> c;
        upd(l, r + 1, c);
        printf(mp.find(seg[1]) != mp.end() ? "Yes\n" : "No\n");
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
Main.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%s", S + 1), C[i] = S + 1;
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     scanf("%d%s", &q, T + 1);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 2364 KB Output is correct
2 Correct 553 ms 2396 KB Output is correct
3 Correct 548 ms 2392 KB Output is correct
4 Correct 562 ms 2424 KB Output is correct
5 Correct 534 ms 2372 KB Output is correct
6 Correct 465 ms 2316 KB Output is correct
7 Correct 550 ms 2376 KB Output is correct
8 Correct 571 ms 2400 KB Output is correct
9 Correct 483 ms 2472 KB Output is correct
10 Correct 513 ms 2364 KB Output is correct
11 Correct 602 ms 2360 KB Output is correct
12 Correct 552 ms 2360 KB Output is correct
13 Correct 470 ms 2400 KB Output is correct
14 Correct 515 ms 2448 KB Output is correct
15 Correct 527 ms 2376 KB Output is correct
16 Correct 638 ms 2392 KB Output is correct
17 Correct 592 ms 2452 KB Output is correct
18 Correct 494 ms 2360 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 2364 KB Output is correct
2 Correct 553 ms 2396 KB Output is correct
3 Correct 548 ms 2392 KB Output is correct
4 Correct 562 ms 2424 KB Output is correct
5 Correct 534 ms 2372 KB Output is correct
6 Correct 465 ms 2316 KB Output is correct
7 Correct 550 ms 2376 KB Output is correct
8 Correct 571 ms 2400 KB Output is correct
9 Correct 483 ms 2472 KB Output is correct
10 Correct 513 ms 2364 KB Output is correct
11 Correct 602 ms 2360 KB Output is correct
12 Correct 552 ms 2360 KB Output is correct
13 Correct 470 ms 2400 KB Output is correct
14 Correct 515 ms 2448 KB Output is correct
15 Correct 527 ms 2376 KB Output is correct
16 Correct 638 ms 2392 KB Output is correct
17 Correct 592 ms 2452 KB Output is correct
18 Correct 494 ms 2360 KB Output is correct
19 Correct 831 ms 7944 KB Output is correct
20 Correct 785 ms 6328 KB Output is correct
21 Correct 673 ms 7864 KB Output is correct
22 Correct 706 ms 7680 KB Output is correct
23 Correct 577 ms 2804 KB Output is correct
24 Correct 574 ms 2776 KB Output is correct
25 Correct 704 ms 7856 KB Output is correct
26 Correct 708 ms 7892 KB Output is correct
27 Correct 801 ms 7920 KB Output is correct
28 Correct 814 ms 7824 KB Output is correct
29 Correct 765 ms 7864 KB Output is correct
30 Correct 626 ms 2908 KB Output is correct
31 Correct 708 ms 8044 KB Output is correct
32 Correct 780 ms 7800 KB Output is correct
33 Correct 578 ms 2752 KB Output is correct
34 Correct 819 ms 7932 KB Output is correct
35 Correct 628 ms 7528 KB Output is correct
36 Correct 573 ms 2776 KB Output is correct
37 Correct 586 ms 2728 KB Output is correct
38 Correct 720 ms 6348 KB Output is correct
39 Correct 616 ms 5908 KB Output is correct
40 Correct 674 ms 5424 KB Output is correct
41 Correct 826 ms 8100 KB Output is correct
42 Correct 474 ms 6040 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 2364 KB Output is correct
2 Correct 553 ms 2396 KB Output is correct
3 Correct 548 ms 2392 KB Output is correct
4 Correct 562 ms 2424 KB Output is correct
5 Correct 534 ms 2372 KB Output is correct
6 Correct 465 ms 2316 KB Output is correct
7 Correct 550 ms 2376 KB Output is correct
8 Correct 571 ms 2400 KB Output is correct
9 Correct 483 ms 2472 KB Output is correct
10 Correct 513 ms 2364 KB Output is correct
11 Correct 602 ms 2360 KB Output is correct
12 Correct 552 ms 2360 KB Output is correct
13 Correct 470 ms 2400 KB Output is correct
14 Correct 515 ms 2448 KB Output is correct
15 Correct 527 ms 2376 KB Output is correct
16 Correct 638 ms 2392 KB Output is correct
17 Correct 592 ms 2452 KB Output is correct
18 Correct 494 ms 2360 KB Output is correct
19 Correct 543 ms 2364 KB Output is correct
20 Correct 512 ms 2452 KB Output is correct
21 Correct 475 ms 2368 KB Output is correct
22 Correct 470 ms 2332 KB Output is correct
23 Correct 510 ms 2448 KB Output is correct
24 Correct 490 ms 2424 KB Output is correct
25 Correct 492 ms 2500 KB Output is correct
26 Correct 527 ms 2380 KB Output is correct
27 Correct 480 ms 2500 KB Output is correct
28 Correct 437 ms 2536 KB Output is correct
29 Correct 491 ms 2420 KB Output is correct
30 Correct 439 ms 2364 KB Output is correct
31 Correct 481 ms 2368 KB Output is correct
32 Correct 513 ms 2384 KB Output is correct
33 Correct 483 ms 2464 KB Output is correct
34 Correct 465 ms 2316 KB Output is correct
35 Correct 502 ms 2552 KB Output is correct
36 Correct 485 ms 2372 KB Output is correct
37 Correct 576 ms 2452 KB Output is correct
38 Correct 531 ms 2472 KB Output is correct
39 Correct 488 ms 2444 KB Output is correct
40 Correct 487 ms 2432 KB Output is correct
41 Correct 487 ms 2520 KB Output is correct
42 Correct 478 ms 2380 KB Output is correct
43 Correct 473 ms 2348 KB Output is correct
44 Correct 495 ms 2392 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 2364 KB Output is correct
2 Correct 553 ms 2396 KB Output is correct
3 Correct 548 ms 2392 KB Output is correct
4 Correct 562 ms 2424 KB Output is correct
5 Correct 534 ms 2372 KB Output is correct
6 Correct 465 ms 2316 KB Output is correct
7 Correct 550 ms 2376 KB Output is correct
8 Correct 571 ms 2400 KB Output is correct
9 Correct 483 ms 2472 KB Output is correct
10 Correct 513 ms 2364 KB Output is correct
11 Correct 602 ms 2360 KB Output is correct
12 Correct 552 ms 2360 KB Output is correct
13 Correct 470 ms 2400 KB Output is correct
14 Correct 515 ms 2448 KB Output is correct
15 Correct 527 ms 2376 KB Output is correct
16 Correct 638 ms 2392 KB Output is correct
17 Correct 592 ms 2452 KB Output is correct
18 Correct 494 ms 2360 KB Output is correct
19 Correct 831 ms 7944 KB Output is correct
20 Correct 785 ms 6328 KB Output is correct
21 Correct 673 ms 7864 KB Output is correct
22 Correct 706 ms 7680 KB Output is correct
23 Correct 577 ms 2804 KB Output is correct
24 Correct 574 ms 2776 KB Output is correct
25 Correct 704 ms 7856 KB Output is correct
26 Correct 708 ms 7892 KB Output is correct
27 Correct 801 ms 7920 KB Output is correct
28 Correct 814 ms 7824 KB Output is correct
29 Correct 765 ms 7864 KB Output is correct
30 Correct 626 ms 2908 KB Output is correct
31 Correct 708 ms 8044 KB Output is correct
32 Correct 780 ms 7800 KB Output is correct
33 Correct 578 ms 2752 KB Output is correct
34 Correct 819 ms 7932 KB Output is correct
35 Correct 628 ms 7528 KB Output is correct
36 Correct 573 ms 2776 KB Output is correct
37 Correct 586 ms 2728 KB Output is correct
38 Correct 720 ms 6348 KB Output is correct
39 Correct 616 ms 5908 KB Output is correct
40 Correct 674 ms 5424 KB Output is correct
41 Correct 826 ms 8100 KB Output is correct
42 Correct 474 ms 6040 KB Output is correct
43 Correct 543 ms 2364 KB Output is correct
44 Correct 512 ms 2452 KB Output is correct
45 Correct 475 ms 2368 KB Output is correct
46 Correct 470 ms 2332 KB Output is correct
47 Correct 510 ms 2448 KB Output is correct
48 Correct 490 ms 2424 KB Output is correct
49 Correct 492 ms 2500 KB Output is correct
50 Correct 527 ms 2380 KB Output is correct
51 Correct 480 ms 2500 KB Output is correct
52 Correct 437 ms 2536 KB Output is correct
53 Correct 491 ms 2420 KB Output is correct
54 Correct 439 ms 2364 KB Output is correct
55 Correct 481 ms 2368 KB Output is correct
56 Correct 513 ms 2384 KB Output is correct
57 Correct 483 ms 2464 KB Output is correct
58 Correct 465 ms 2316 KB Output is correct
59 Correct 502 ms 2552 KB Output is correct
60 Correct 485 ms 2372 KB Output is correct
61 Correct 576 ms 2452 KB Output is correct
62 Correct 531 ms 2472 KB Output is correct
63 Correct 488 ms 2444 KB Output is correct
64 Correct 487 ms 2432 KB Output is correct
65 Correct 487 ms 2520 KB Output is correct
66 Correct 478 ms 2380 KB Output is correct
67 Correct 473 ms 2348 KB Output is correct
68 Correct 495 ms 2392 KB Output is correct
69 Correct 892 ms 9692 KB Output is correct
70 Correct 852 ms 8708 KB Output is correct
71 Correct 596 ms 2808 KB Output is correct
72 Correct 596 ms 2820 KB Output is correct
73 Correct 597 ms 2828 KB Output is correct
74 Correct 655 ms 8184 KB Output is correct
75 Correct 593 ms 2812 KB Output is correct
76 Correct 731 ms 8440 KB Output is correct
77 Correct 660 ms 8224 KB Output is correct
78 Correct 563 ms 2744 KB Output is correct
79 Correct 579 ms 2808 KB Output is correct
80 Correct 703 ms 9192 KB Output is correct
81 Correct 590 ms 2820 KB Output is correct
82 Correct 764 ms 10272 KB Output is correct
83 Correct 760 ms 9952 KB Output is correct
84 Correct 570 ms 2924 KB Output is correct
85 Correct 571 ms 2812 KB Output is correct
86 Correct 741 ms 9400 KB Output is correct
87 Correct 858 ms 10260 KB Output is correct
88 Correct 592 ms 2884 KB Output is correct
89 Correct 746 ms 9776 KB Output is correct
90 Correct 824 ms 10212 KB Output is correct
91 Correct 584 ms 2816 KB Output is correct
92 Correct 711 ms 9308 KB Output is correct
93 Correct 574 ms 2956 KB Output is correct
94 Correct 593 ms 2888 KB Output is correct
95 Correct 586 ms 2840 KB Output is correct
96 Correct 703 ms 6280 KB Output is correct
97 Correct 694 ms 8444 KB Output is correct
98 Correct 699 ms 6916 KB Output is correct
99 Correct 895 ms 10588 KB Output is correct
100 Correct 567 ms 8328 KB Output is correct