oj.uz

Submission #420198

# Submission time Handle Problem Language Result Execution time Memory
420198 2021-06-08T07:34:05 Z Mamedov Crossing (JOI21_crossing) C++17
100 / 100
 991 ms 11712 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define ui unsigned int
#define ull unsigned long long
#define f first
#define s second
#define oo 1000000000

using namespace std;


const int mod = 987657683;
const int up = 2e5 + 5;

int tree[up << 2], lazy[up << 2], pref[up];
string T;

map<char, int> num = {
    {'J', 0},
    {'O', 1},
    {'I', 2}
};

void pre_clc() {
    pref[0] = 0;
    pref[1] = 1;
    for(int i = 2; i < up; ++i) {
        pref[i] = (3ll * pref[i - 1]) % mod;
    }
    for(int i = 2; i < up; ++i) {
        pref[i] += pref[i - 1];
        if(pref[i] >= mod) pref[i] -= mod;
    }
}

int rangeHash(int l, int r) {
    return (pref[r] - pref[l - 1] + mod) % mod;
}

void build(int node, int l, int r) {
    if(l == r) {
        tree[node] = (num[T[l - 1]] * rangeHash(l, r)) % mod;
    }else {
        int mid = (l + r) >> 1;
        build(node << 1, l, mid);
        build((node << 1) | 1, mid + 1, r);
        tree[node] = (tree[node << 1] + tree[(node << 1) | 1]) % mod;
    }
}

void relax(int node, int l, int r) {
    if(l != r) {
        lazy[node << 1] = lazy[(node << 1) | 1] = lazy[node];
    }
    tree[node] = (lazy[node] * rangeHash(l, r)) % mod;
    lazy[node] = -1;
}

void update(int node, int l, int r, int ul, int ur, int val) {
    if(lazy[node] != -1) relax(node, l, r);
    if(l > ur || ul > r) return;
    if(ul <= l && r <= ur) {
        lazy[node] = val;
        relax(node, l, r);
    }else {
        int mid = (l + r) >> 1;
        update(node << 1, l, mid, ul, ur, val);
        update((node << 1) | 1, mid + 1, r, ul, ur, val);
        tree[node] = (tree[node << 1] + tree[(node << 1) | 1]) % mod;
    }
}

string Merge(string &s1, string &s2) {
    int n = (int)s1.size();
    string res;
    for(int i = 0; i < n; ++i) {
        if(s1[i] == s2[i]) {
            res += s1[i];
        }else {
            res += ('J' + 'O' + 'I' - s1[i] - s2[i]);
        }
    }
    return res;
}

int Hash(string s) {
    int n = (int)s.size();
    int res = 0;
    for(int i = 1; i <= n; ++i) {
        res += (num[s[i - 1]] * rangeHash(i, i)) % mod;
        if(res >= mod) res -= mod;
    }
    return res;
}
void solve() {
    pre_clc();
    int n;
    string s[3];
    cin >> n;
    cin >> s[0] >> s[1] >> s[2];
    set<string>st, tmp;
    tmp.insert(s[0]);
    tmp.insert(s[1]);
    tmp.insert(s[2]);

    bool has_new = true;
    while(has_new) {
        has_new = false;
        for(string s1 : tmp) {
            for(string s2 : tmp) {
                st.insert(Merge(s1, s2));
            }
        }
        if(st.size() > tmp.size()) {
            has_new = true;
        }
        tmp = st;
    }
    set<int>hasHash;
    for(string any : st) {
        hasHash.insert(Hash(any));
    }
    int q, l, r;
    char ch;
    cin >> q;
    cin >> T;
    memset(lazy, -1, sizeof(lazy));
    build(1, 1, n);
    if(hasHash.find(tree[1]) != hasHash.end()) {
        cout << "Yes\n";
    }else {
        cout << "No\n";
    }
    for(int i = 0; i < q; ++i) {
        cin >> l >> r >> ch;
        update(1, 1, n, l, r, num[ch]);
        if(hasHash.find(tree[1]) != hasHash.end()) {
        cout << "Yes\n";
        }else {
            cout << "No\n";
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 4724 KB Output is correct
2 Correct 412 ms 4804 KB Output is correct
3 Correct 430 ms 4768 KB Output is correct
4 Correct 393 ms 4928 KB Output is correct
5 Correct 397 ms 4744 KB Output is correct
6 Correct 395 ms 4784 KB Output is correct
7 Correct 393 ms 4696 KB Output is correct
8 Correct 398 ms 4764 KB Output is correct
9 Correct 410 ms 4804 KB Output is correct
10 Correct 414 ms 4740 KB Output is correct
11 Correct 408 ms 4800 KB Output is correct
12 Correct 402 ms 4804 KB Output is correct
13 Correct 427 ms 4836 KB Output is correct
14 Correct 411 ms 4804 KB Output is correct
15 Correct 405 ms 4720 KB Output is correct
16 Correct 400 ms 4764 KB Output is correct
17 Correct 413 ms 4812 KB Output is correct
18 Correct 434 ms 4820 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 4724 KB Output is correct
2 Correct 412 ms 4804 KB Output is correct
3 Correct 430 ms 4768 KB Output is correct
4 Correct 393 ms 4928 KB Output is correct
5 Correct 397 ms 4744 KB Output is correct
6 Correct 395 ms 4784 KB Output is correct
7 Correct 393 ms 4696 KB Output is correct
8 Correct 398 ms 4764 KB Output is correct
9 Correct 410 ms 4804 KB Output is correct
10 Correct 414 ms 4740 KB Output is correct
11 Correct 408 ms 4800 KB Output is correct
12 Correct 402 ms 4804 KB Output is correct
13 Correct 427 ms 4836 KB Output is correct
14 Correct 411 ms 4804 KB Output is correct
15 Correct 405 ms 4720 KB Output is correct
16 Correct 400 ms 4764 KB Output is correct
17 Correct 413 ms 4812 KB Output is correct
18 Correct 434 ms 4820 KB Output is correct
19 Correct 709 ms 8200 KB Output is correct
20 Correct 663 ms 8256 KB Output is correct
21 Correct 502 ms 8068 KB Output is correct
22 Correct 510 ms 8016 KB Output is correct
23 Correct 460 ms 4968 KB Output is correct
24 Correct 457 ms 5028 KB Output is correct
25 Correct 556 ms 8264 KB Output is correct
26 Correct 615 ms 8328 KB Output is correct
27 Correct 616 ms 8276 KB Output is correct
28 Correct 587 ms 8180 KB Output is correct
29 Correct 590 ms 8216 KB Output is correct
30 Correct 480 ms 5112 KB Output is correct
31 Correct 601 ms 8280 KB Output is correct
32 Correct 579 ms 7988 KB Output is correct
33 Correct 464 ms 5184 KB Output is correct
34 Correct 593 ms 8276 KB Output is correct
35 Correct 493 ms 7844 KB Output is correct
36 Correct 472 ms 5020 KB Output is correct
37 Correct 499 ms 5040 KB Output is correct
38 Correct 640 ms 8228 KB Output is correct
39 Correct 505 ms 8268 KB Output is correct
40 Correct 649 ms 6780 KB Output is correct
41 Correct 748 ms 8444 KB Output is correct
42 Correct 387 ms 8564 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 4724 KB Output is correct
2 Correct 412 ms 4804 KB Output is correct
3 Correct 430 ms 4768 KB Output is correct
4 Correct 393 ms 4928 KB Output is correct
5 Correct 397 ms 4744 KB Output is correct
6 Correct 395 ms 4784 KB Output is correct
7 Correct 393 ms 4696 KB Output is correct
8 Correct 398 ms 4764 KB Output is correct
9 Correct 410 ms 4804 KB Output is correct
10 Correct 414 ms 4740 KB Output is correct
11 Correct 408 ms 4800 KB Output is correct
12 Correct 402 ms 4804 KB Output is correct
13 Correct 427 ms 4836 KB Output is correct
14 Correct 411 ms 4804 KB Output is correct
15 Correct 405 ms 4720 KB Output is correct
16 Correct 400 ms 4764 KB Output is correct
17 Correct 413 ms 4812 KB Output is correct
18 Correct 434 ms 4820 KB Output is correct
19 Correct 441 ms 4788 KB Output is correct
20 Correct 424 ms 4744 KB Output is correct
21 Correct 417 ms 4800 KB Output is correct
22 Correct 389 ms 4764 KB Output is correct
23 Correct 408 ms 4788 KB Output is correct
24 Correct 395 ms 4804 KB Output is correct
25 Correct 405 ms 4812 KB Output is correct
26 Correct 400 ms 4788 KB Output is correct
27 Correct 409 ms 4736 KB Output is correct
28 Correct 388 ms 4656 KB Output is correct
29 Correct 500 ms 4796 KB Output is correct
30 Correct 383 ms 4796 KB Output is correct
31 Correct 412 ms 4804 KB Output is correct
32 Correct 446 ms 4764 KB Output is correct
33 Correct 433 ms 4852 KB Output is correct
34 Correct 389 ms 4696 KB Output is correct
35 Correct 414 ms 4744 KB Output is correct
36 Correct 466 ms 4700 KB Output is correct
37 Correct 443 ms 4800 KB Output is correct
38 Correct 403 ms 4828 KB Output is correct
39 Correct 405 ms 4804 KB Output is correct
40 Correct 422 ms 4832 KB Output is correct
41 Correct 419 ms 4704 KB Output is correct
42 Correct 430 ms 4908 KB Output is correct
43 Correct 395 ms 4800 KB Output is correct
44 Correct 408 ms 4804 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 4724 KB Output is correct
2 Correct 412 ms 4804 KB Output is correct
3 Correct 430 ms 4768 KB Output is correct
4 Correct 393 ms 4928 KB Output is correct
5 Correct 397 ms 4744 KB Output is correct
6 Correct 395 ms 4784 KB Output is correct
7 Correct 393 ms 4696 KB Output is correct
8 Correct 398 ms 4764 KB Output is correct
9 Correct 410 ms 4804 KB Output is correct
10 Correct 414 ms 4740 KB Output is correct
11 Correct 408 ms 4800 KB Output is correct
12 Correct 402 ms 4804 KB Output is correct
13 Correct 427 ms 4836 KB Output is correct
14 Correct 411 ms 4804 KB Output is correct
15 Correct 405 ms 4720 KB Output is correct
16 Correct 400 ms 4764 KB Output is correct
17 Correct 413 ms 4812 KB Output is correct
18 Correct 434 ms 4820 KB Output is correct
19 Correct 709 ms 8200 KB Output is correct
20 Correct 663 ms 8256 KB Output is correct
21 Correct 502 ms 8068 KB Output is correct
22 Correct 510 ms 8016 KB Output is correct
23 Correct 460 ms 4968 KB Output is correct
24 Correct 457 ms 5028 KB Output is correct
25 Correct 556 ms 8264 KB Output is correct
26 Correct 615 ms 8328 KB Output is correct
27 Correct 616 ms 8276 KB Output is correct
28 Correct 587 ms 8180 KB Output is correct
29 Correct 590 ms 8216 KB Output is correct
30 Correct 480 ms 5112 KB Output is correct
31 Correct 601 ms 8280 KB Output is correct
32 Correct 579 ms 7988 KB Output is correct
33 Correct 464 ms 5184 KB Output is correct
34 Correct 593 ms 8276 KB Output is correct
35 Correct 493 ms 7844 KB Output is correct
36 Correct 472 ms 5020 KB Output is correct
37 Correct 499 ms 5040 KB Output is correct
38 Correct 640 ms 8228 KB Output is correct
39 Correct 505 ms 8268 KB Output is correct
40 Correct 649 ms 6780 KB Output is correct
41 Correct 748 ms 8444 KB Output is correct
42 Correct 387 ms 8564 KB Output is correct
43 Correct 441 ms 4788 KB Output is correct
44 Correct 424 ms 4744 KB Output is correct
45 Correct 417 ms 4800 KB Output is correct
46 Correct 389 ms 4764 KB Output is correct
47 Correct 408 ms 4788 KB Output is correct
48 Correct 395 ms 4804 KB Output is correct
49 Correct 405 ms 4812 KB Output is correct
50 Correct 400 ms 4788 KB Output is correct
51 Correct 409 ms 4736 KB Output is correct
52 Correct 388 ms 4656 KB Output is correct
53 Correct 500 ms 4796 KB Output is correct
54 Correct 383 ms 4796 KB Output is correct
55 Correct 412 ms 4804 KB Output is correct
56 Correct 446 ms 4764 KB Output is correct
57 Correct 433 ms 4852 KB Output is correct
58 Correct 389 ms 4696 KB Output is correct
59 Correct 414 ms 4744 KB Output is correct
60 Correct 466 ms 4700 KB Output is correct
61 Correct 443 ms 4800 KB Output is correct
62 Correct 403 ms 4828 KB Output is correct
63 Correct 405 ms 4804 KB Output is correct
64 Correct 422 ms 4832 KB Output is correct
65 Correct 419 ms 4704 KB Output is correct
66 Correct 430 ms 4908 KB Output is correct
67 Correct 395 ms 4800 KB Output is correct
68 Correct 408 ms 4804 KB Output is correct
69 Correct 816 ms 10824 KB Output is correct
70 Correct 978 ms 11640 KB Output is correct
71 Correct 468 ms 5092 KB Output is correct
72 Correct 493 ms 5144 KB Output is correct
73 Correct 476 ms 5088 KB Output is correct
74 Correct 541 ms 8684 KB Output is correct
75 Correct 499 ms 5000 KB Output is correct
76 Correct 563 ms 9248 KB Output is correct
77 Correct 558 ms 8780 KB Output is correct
78 Correct 482 ms 5112 KB Output is correct
79 Correct 457 ms 5092 KB Output is correct
80 Correct 727 ms 10372 KB Output is correct
81 Correct 484 ms 5204 KB Output is correct
82 Correct 911 ms 11468 KB Output is correct
83 Correct 877 ms 11336 KB Output is correct
84 Correct 475 ms 5160 KB Output is correct
85 Correct 480 ms 5168 KB Output is correct
86 Correct 737 ms 10716 KB Output is correct
87 Correct 818 ms 11516 KB Output is correct
88 Correct 482 ms 5248 KB Output is correct
89 Correct 681 ms 11140 KB Output is correct
90 Correct 781 ms 11452 KB Output is correct
91 Correct 501 ms 5256 KB Output is correct
92 Correct 699 ms 10672 KB Output is correct
93 Correct 490 ms 5128 KB Output is correct
94 Correct 485 ms 5256 KB Output is correct
95 Correct 467 ms 5244 KB Output is correct
96 Correct 606 ms 8332 KB Output is correct
97 Correct 675 ms 11528 KB Output is correct
98 Correct 704 ms 9304 KB Output is correct
99 Correct 991 ms 11712 KB Output is correct
100 Correct 671 ms 11652 KB Output is correct