oj.uz

Submission #895236

# Submission time Handle Problem Language Result Execution time Memory
895236 2023-12-29T16:13:52 Z Alcabel Crossing (JOI21_crossing) C++17
100 / 100
 1409 ms 17816 KB 
#include <bits/stdc++.h>
using namespace std;

struct SegTree {
    int n, N;
    vector<char> sym, lazy;
    vector<bool> same;
    SegTree() {}
    SegTree(int _n, const string& s) {
        n = _n, N = 1;
        while (N < n) {
            N <<= 1;
        }
        sym.resize(2 * N, -2);
        same.resize(2 * N, true);
        lazy.resize(2 * N, -1);
        for (int i = 0; i < n; ++i) {
            sym[N + i] = s[i];
            // cerr << "v: " << N + i << ", sym: " << st[N + i].sym << '\n';
        }
        for (int i = N - 1; i > 0; --i) {
            if (sym[2 * i] == -2) {
                sym[i] = sym[2 * i + 1];
            } else if (sym[2 * i + 1] == -2) {
                sym[i] = sym[2 * i];
            } else {
                if (sym[2 * i] == -1 || sym[2 * i + 1] == -1 || sym[2 * i] != sym[2 * i + 1]) {
                    sym[i] = -1;
                } else {
                    sym[i] = sym[2 * i];
                }
            }
            // cerr << "v: " << i << ", sym: " << st[i].sym << '\n';
        }
    }
    void push(int v) {
        // cerr << "v: " << v << ", lazy: " << lazy[v] << ' ';
        if (sym[v] == lazy[v]) {
            same[v] = true;
        } else {
            same[v] = false;
        }
        // cerr << "same: " << st[v].same << '\n';
        if (v < N) {
            lazy[2 * v] = lazy[v];
            lazy[2 * v + 1] = lazy[v];
        }
        lazy[v] = -1;
    }
    void assign(int v, int tl, int tr, int l, int r, char c) {
        if (lazy[v] != -1) {
            push(v);
        }
        if (tl >= r || tr <= l) {
            return;
        }
        if (l <= tl && tr <= r) {
            lazy[v] = c;
            push(v);
            return;
        }
        int m = tl + (tr - tl) / 2;
        assign(2 * v, tl, m, l, r, c);
        assign(2 * v + 1, m, tr, l, r, c);
        same[v] = same[2 * v] && same[2 * v + 1];
        // cerr << "v: " << v << ", same: " << st[v].same << '\n';
    }
    void assign(int l, int r, char c) {
        assign(1, 0, N, l, r, c);
    }
    bool query() {
        if (lazy[1] != -1) {
            push(1);
        }
        return same[1];
    }
    ~SegTree() {}
};

void solve() {
    int n;
    cin >> n;
    vector<string> s(3);
    for (int i = 0; i < 3; ++i) {
        cin >> s[i];
    }
    for (int i = 0; i < 2; ++i) {
        for (int j = i + 1; j < 3; ++j) {
            s.emplace_back(string(n, '.'));
            for (int pos = 0; pos < n; ++pos) {
                if (s[i][pos] == s[j][pos]) {
                    s.back()[pos] = s[j][pos];
                } else {
                    s.back()[pos] = 'J' + 'O' + 'I' - s[i][pos] - s[j][pos];
                }
            }
            int k = 3 - i - j;
            s.emplace_back(string(n, '.'));
            for (int pos = 0; pos < n; ++pos) {
                if (s[(int)s.size() - 2][pos] == s[k][pos]) {
                    s.back()[pos] = s[k][pos];
                } else {
                    s.back()[pos] = 'J' + 'O' + 'I' - s[(int)s.size() - 2][pos] - s[k][pos];
                }
            }
        }
    }
    int q;
    cin >> q;
    string t;
    cin >> t;
    vector<SegTree> st(9);
    for (int i = 0; i < 9; ++i) {
        st[i] = SegTree(n, s[i]);
        for (int pos = 0; pos < n; ++pos) {
            st[i].assign(pos, pos + 1, t[pos]);
        }
    }
    auto query = [&]() -> bool {
        for (int i = 0; i < 9; ++i) {
            if (st[i].query()) {
                return true;
            }
        }
        return false;
    };
    if (query()) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    while (q--) {
        int l, r;
        char c;
        cin >> l >> r >> c;
        --l;
        for (int i = 0; i < 9; ++i) {
            st[i].assign(l, r, c);
        }
        if (query()) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 2384 KB Output is correct
2 Correct 249 ms 2348 KB Output is correct
3 Correct 272 ms 2388 KB Output is correct
4 Correct 194 ms 2264 KB Output is correct
5 Correct 183 ms 2436 KB Output is correct
6 Correct 188 ms 2420 KB Output is correct
7 Correct 194 ms 2384 KB Output is correct
8 Correct 191 ms 2556 KB Output is correct
9 Correct 192 ms 2388 KB Output is correct
10 Correct 194 ms 2568 KB Output is correct
11 Correct 217 ms 2516 KB Output is correct
12 Correct 192 ms 2408 KB Output is correct
13 Correct 205 ms 2432 KB Output is correct
14 Correct 191 ms 2564 KB Output is correct
15 Correct 194 ms 2384 KB Output is correct
16 Correct 193 ms 2388 KB Output is correct
17 Correct 207 ms 2692 KB Output is correct
18 Correct 237 ms 2388 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 2384 KB Output is correct
2 Correct 249 ms 2348 KB Output is correct
3 Correct 272 ms 2388 KB Output is correct
4 Correct 194 ms 2264 KB Output is correct
5 Correct 183 ms 2436 KB Output is correct
6 Correct 188 ms 2420 KB Output is correct
7 Correct 194 ms 2384 KB Output is correct
8 Correct 191 ms 2556 KB Output is correct
9 Correct 192 ms 2388 KB Output is correct
10 Correct 194 ms 2568 KB Output is correct
11 Correct 217 ms 2516 KB Output is correct
12 Correct 192 ms 2408 KB Output is correct
13 Correct 205 ms 2432 KB Output is correct
14 Correct 191 ms 2564 KB Output is correct
15 Correct 194 ms 2384 KB Output is correct
16 Correct 193 ms 2388 KB Output is correct
17 Correct 207 ms 2692 KB Output is correct
18 Correct 237 ms 2388 KB Output is correct
19 Correct 1217 ms 17448 KB Output is correct
20 Correct 1233 ms 17604 KB Output is correct
21 Correct 843 ms 17020 KB Output is correct
22 Correct 791 ms 16820 KB Output is correct
23 Correct 365 ms 4184 KB Output is correct
24 Correct 380 ms 4008 KB Output is correct
25 Correct 943 ms 17564 KB Output is correct
26 Correct 937 ms 17516 KB Output is correct
27 Correct 1063 ms 17488 KB Output is correct
28 Correct 1004 ms 17556 KB Output is correct
29 Correct 1004 ms 17340 KB Output is correct
30 Correct 419 ms 4176 KB Output is correct
31 Correct 1028 ms 17564 KB Output is correct
32 Correct 928 ms 17092 KB Output is correct
33 Correct 376 ms 3920 KB Output is correct
34 Correct 995 ms 17448 KB Output is correct
35 Correct 699 ms 16464 KB Output is correct
36 Correct 368 ms 4176 KB Output is correct
37 Correct 364 ms 4104 KB Output is correct
38 Correct 1108 ms 17760 KB Output is correct
39 Correct 716 ms 17588 KB Output is correct
40 Correct 671 ms 11004 KB Output is correct
41 Correct 1404 ms 17748 KB Output is correct
42 Correct 602 ms 16944 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 2384 KB Output is correct
2 Correct 249 ms 2348 KB Output is correct
3 Correct 272 ms 2388 KB Output is correct
4 Correct 194 ms 2264 KB Output is correct
5 Correct 183 ms 2436 KB Output is correct
6 Correct 188 ms 2420 KB Output is correct
7 Correct 194 ms 2384 KB Output is correct
8 Correct 191 ms 2556 KB Output is correct
9 Correct 192 ms 2388 KB Output is correct
10 Correct 194 ms 2568 KB Output is correct
11 Correct 217 ms 2516 KB Output is correct
12 Correct 192 ms 2408 KB Output is correct
13 Correct 205 ms 2432 KB Output is correct
14 Correct 191 ms 2564 KB Output is correct
15 Correct 194 ms 2384 KB Output is correct
16 Correct 193 ms 2388 KB Output is correct
17 Correct 207 ms 2692 KB Output is correct
18 Correct 237 ms 2388 KB Output is correct
19 Correct 263 ms 2384 KB Output is correct
20 Correct 318 ms 2384 KB Output is correct
21 Correct 219 ms 2576 KB Output is correct
22 Correct 194 ms 2336 KB Output is correct
23 Correct 216 ms 2492 KB Output is correct
24 Correct 226 ms 2372 KB Output is correct
25 Correct 222 ms 2472 KB Output is correct
26 Correct 206 ms 2308 KB Output is correct
27 Correct 230 ms 2384 KB Output is correct
28 Correct 200 ms 2128 KB Output is correct
29 Correct 225 ms 2640 KB Output is correct
30 Correct 198 ms 2264 KB Output is correct
31 Correct 224 ms 2560 KB Output is correct
32 Correct 226 ms 2316 KB Output is correct
33 Correct 239 ms 2408 KB Output is correct
34 Correct 213 ms 2552 KB Output is correct
35 Correct 224 ms 2388 KB Output is correct
36 Correct 262 ms 2488 KB Output is correct
37 Correct 227 ms 2580 KB Output is correct
38 Correct 240 ms 2336 KB Output is correct
39 Correct 226 ms 2388 KB Output is correct
40 Correct 237 ms 2564 KB Output is correct
41 Correct 228 ms 2384 KB Output is correct
42 Correct 234 ms 2488 KB Output is correct
43 Correct 228 ms 2524 KB Output is correct
44 Correct 245 ms 2572 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 2384 KB Output is correct
2 Correct 249 ms 2348 KB Output is correct
3 Correct 272 ms 2388 KB Output is correct
4 Correct 194 ms 2264 KB Output is correct
5 Correct 183 ms 2436 KB Output is correct
6 Correct 188 ms 2420 KB Output is correct
7 Correct 194 ms 2384 KB Output is correct
8 Correct 191 ms 2556 KB Output is correct
9 Correct 192 ms 2388 KB Output is correct
10 Correct 194 ms 2568 KB Output is correct
11 Correct 217 ms 2516 KB Output is correct
12 Correct 192 ms 2408 KB Output is correct
13 Correct 205 ms 2432 KB Output is correct
14 Correct 191 ms 2564 KB Output is correct
15 Correct 194 ms 2384 KB Output is correct
16 Correct 193 ms 2388 KB Output is correct
17 Correct 207 ms 2692 KB Output is correct
18 Correct 237 ms 2388 KB Output is correct
19 Correct 1217 ms 17448 KB Output is correct
20 Correct 1233 ms 17604 KB Output is correct
21 Correct 843 ms 17020 KB Output is correct
22 Correct 791 ms 16820 KB Output is correct
23 Correct 365 ms 4184 KB Output is correct
24 Correct 380 ms 4008 KB Output is correct
25 Correct 943 ms 17564 KB Output is correct
26 Correct 937 ms 17516 KB Output is correct
27 Correct 1063 ms 17488 KB Output is correct
28 Correct 1004 ms 17556 KB Output is correct
29 Correct 1004 ms 17340 KB Output is correct
30 Correct 419 ms 4176 KB Output is correct
31 Correct 1028 ms 17564 KB Output is correct
32 Correct 928 ms 17092 KB Output is correct
33 Correct 376 ms 3920 KB Output is correct
34 Correct 995 ms 17448 KB Output is correct
35 Correct 699 ms 16464 KB Output is correct
36 Correct 368 ms 4176 KB Output is correct
37 Correct 364 ms 4104 KB Output is correct
38 Correct 1108 ms 17760 KB Output is correct
39 Correct 716 ms 17588 KB Output is correct
40 Correct 671 ms 11004 KB Output is correct
41 Correct 1404 ms 17748 KB Output is correct
42 Correct 602 ms 16944 KB Output is correct
43 Correct 263 ms 2384 KB Output is correct
44 Correct 318 ms 2384 KB Output is correct
45 Correct 219 ms 2576 KB Output is correct
46 Correct 194 ms 2336 KB Output is correct
47 Correct 216 ms 2492 KB Output is correct
48 Correct 226 ms 2372 KB Output is correct
49 Correct 222 ms 2472 KB Output is correct
50 Correct 206 ms 2308 KB Output is correct
51 Correct 230 ms 2384 KB Output is correct
52 Correct 200 ms 2128 KB Output is correct
53 Correct 225 ms 2640 KB Output is correct
54 Correct 198 ms 2264 KB Output is correct
55 Correct 224 ms 2560 KB Output is correct
56 Correct 226 ms 2316 KB Output is correct
57 Correct 239 ms 2408 KB Output is correct
58 Correct 213 ms 2552 KB Output is correct
59 Correct 224 ms 2388 KB Output is correct
60 Correct 262 ms 2488 KB Output is correct
61 Correct 227 ms 2580 KB Output is correct
62 Correct 240 ms 2336 KB Output is correct
63 Correct 226 ms 2388 KB Output is correct
64 Correct 237 ms 2564 KB Output is correct
65 Correct 228 ms 2384 KB Output is correct
66 Correct 234 ms 2488 KB Output is correct
67 Correct 228 ms 2524 KB Output is correct
68 Correct 245 ms 2572 KB Output is correct
69 Correct 1409 ms 16660 KB Output is correct
70 Correct 1323 ms 17772 KB Output is correct
71 Correct 438 ms 4056 KB Output is correct
72 Correct 395 ms 4108 KB Output is correct
73 Correct 394 ms 4120 KB Output is correct
74 Correct 750 ms 16680 KB Output is correct
75 Correct 399 ms 3988 KB Output is correct
76 Correct 898 ms 17540 KB Output is correct
77 Correct 850 ms 17172 KB Output is correct
78 Correct 388 ms 4064 KB Output is correct
79 Correct 403 ms 4192 KB Output is correct
80 Correct 785 ms 16516 KB Output is correct
81 Correct 402 ms 4020 KB Output is correct
82 Correct 928 ms 17816 KB Output is correct
83 Correct 951 ms 17404 KB Output is correct
84 Correct 418 ms 3936 KB Output is correct
85 Correct 427 ms 4064 KB Output is correct
86 Correct 1031 ms 16812 KB Output is correct
87 Correct 1093 ms 17484 KB Output is correct
88 Correct 507 ms 4180 KB Output is correct
89 Correct 942 ms 17228 KB Output is correct
90 Correct 1109 ms 17460 KB Output is correct
91 Correct 468 ms 4128 KB Output is correct
92 Correct 754 ms 16708 KB Output is correct
93 Correct 411 ms 4164 KB Output is correct
94 Correct 402 ms 3924 KB Output is correct
95 Correct 411 ms 4236 KB Output is correct
96 Correct 1210 ms 17348 KB Output is correct
97 Correct 745 ms 17640 KB Output is correct
98 Correct 737 ms 11124 KB Output is correct
99 Correct 1395 ms 17568 KB Output is correct
100 Correct 623 ms 16904 KB Output is correct