oj.uz

Submission #894953

# Submission time Handle Problem Language Result Execution time Memory
894953 2023-12-29T09:42:46 Z Alcabel Crossing (JOI21_crossing) C++17
26 / 100
 191 ms 7000 KB 
#include <bits/stdc++.h>
using namespace std;

struct Cell {
    char sym;
    bool same;
    Cell() { sym = -2, same = true; }
    Cell operator+(const Cell& other) const {
        if (sym == -2) {
            return other;
        }
        if (other.sym == -2) {
            return *this;
        }
        Cell res;
        if (sym == -1 || other.sym == -1 || sym != other.sym) {
            res.sym = -1;
        } else {
            res.sym = sym;
        }
        res.same = same && other.same;
        return res;
    }
    ~Cell() {}
};

struct SegTree {
    int n, N;
    vector<char> lazy;
    vector<Cell> st;
    SegTree() {}
    SegTree(int _n, const string& s) {
        n = _n, N = 1;
        while (N < n) {
            N <<= 1;
        }
        st.resize(2 * N);
        lazy.resize(2 * N, -1);
        for (int i = 0; i < n; ++i) {
            st[N + i].sym = s[i];
            // cerr << "v: " << N + i << ", sym: " << st[N + i].sym << '\n';
        }
        for (int i = N - 1; i > 0; --i) {
            st[i] = st[2 * i] + st[2 * i + 1];
            // cerr << "v: " << i << ", sym: " << st[i].sym << '\n';
        }
    }
    void push(int v) {
        // cerr << "v: " << v << ", lazy: " << lazy[v] << ' ';
        if (st[v].sym == lazy[v]) {
            st[v].same = true;
        } else {
            st[v].same = 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);
        st[v] = st[2 * v] + st[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 st[1].same;
    }
    ~SegTree() {}
};

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s >> s >> s;
    int q;
    cin >> q;
    string t;
    cin >> t;
    SegTree st(n, s);
    for (int i = 0; i < n; ++i) {
        st.assign(i, i + 1, t[i]);
    }
    if (st.query()) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    while (q--) {
        int l, r;
        char c;
        cin >> l >> r >> c;
        --l;
        st.assign(l, r, c);
        if (st.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 51 ms 2392 KB Output is correct
2 Correct 57 ms 2388 KB Output is correct
3 Correct 54 ms 2384 KB Output is correct
4 Correct 50 ms 2388 KB Output is correct
5 Correct 48 ms 2456 KB Output is correct
6 Correct 63 ms 2356 KB Output is correct
7 Correct 50 ms 2384 KB Output is correct
8 Correct 53 ms 2580 KB Output is correct
9 Correct 56 ms 2536 KB Output is correct
10 Correct 50 ms 2524 KB Output is correct
11 Correct 51 ms 2388 KB Output is correct
12 Correct 50 ms 2384 KB Output is correct
13 Correct 54 ms 2568 KB Output is correct
14 Correct 50 ms 2392 KB Output is correct
15 Correct 51 ms 2432 KB Output is correct
16 Correct 51 ms 2380 KB Output is correct
17 Correct 58 ms 2432 KB Output is correct
18 Correct 61 ms 2564 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2392 KB Output is correct
2 Correct 57 ms 2388 KB Output is correct
3 Correct 54 ms 2384 KB Output is correct
4 Correct 50 ms 2388 KB Output is correct
5 Correct 48 ms 2456 KB Output is correct
6 Correct 63 ms 2356 KB Output is correct
7 Correct 50 ms 2384 KB Output is correct
8 Correct 53 ms 2580 KB Output is correct
9 Correct 56 ms 2536 KB Output is correct
10 Correct 50 ms 2524 KB Output is correct
11 Correct 51 ms 2388 KB Output is correct
12 Correct 50 ms 2384 KB Output is correct
13 Correct 54 ms 2568 KB Output is correct
14 Correct 50 ms 2392 KB Output is correct
15 Correct 51 ms 2432 KB Output is correct
16 Correct 51 ms 2380 KB Output is correct
17 Correct 58 ms 2432 KB Output is correct
18 Correct 61 ms 2564 KB Output is correct
19 Correct 170 ms 6792 KB Output is correct
20 Correct 191 ms 6536 KB Output is correct
21 Correct 154 ms 6508 KB Output is correct
22 Correct 128 ms 6140 KB Output is correct
23 Correct 80 ms 3408 KB Output is correct
24 Correct 79 ms 3488 KB Output is correct
25 Correct 137 ms 6788 KB Output is correct
26 Correct 137 ms 6792 KB Output is correct
27 Correct 154 ms 6592 KB Output is correct
28 Correct 164 ms 6672 KB Output is correct
29 Correct 173 ms 6524 KB Output is correct
30 Correct 90 ms 3444 KB Output is correct
31 Correct 160 ms 6668 KB Output is correct
32 Correct 174 ms 6384 KB Output is correct
33 Correct 80 ms 3416 KB Output is correct
34 Correct 154 ms 6608 KB Output is correct
35 Correct 116 ms 6056 KB Output is correct
36 Correct 89 ms 3484 KB Output is correct
37 Correct 80 ms 3332 KB Output is correct
38 Correct 164 ms 6536 KB Output is correct
39 Correct 126 ms 6784 KB Output is correct
40 Correct 113 ms 5388 KB Output is correct
41 Correct 188 ms 7000 KB Output is correct
42 Correct 95 ms 6076 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2392 KB Output is correct
2 Correct 57 ms 2388 KB Output is correct
3 Correct 54 ms 2384 KB Output is correct
4 Correct 50 ms 2388 KB Output is correct
5 Correct 48 ms 2456 KB Output is correct
6 Correct 63 ms 2356 KB Output is correct
7 Correct 50 ms 2384 KB Output is correct
8 Correct 53 ms 2580 KB Output is correct
9 Correct 56 ms 2536 KB Output is correct
10 Correct 50 ms 2524 KB Output is correct
11 Correct 51 ms 2388 KB Output is correct
12 Correct 50 ms 2384 KB Output is correct
13 Correct 54 ms 2568 KB Output is correct
14 Correct 50 ms 2392 KB Output is correct
15 Correct 51 ms 2432 KB Output is correct
16 Correct 51 ms 2380 KB Output is correct
17 Correct 58 ms 2432 KB Output is correct
18 Correct 61 ms 2564 KB Output is correct
19 Correct 54 ms 2440 KB Output is correct
20 Correct 64 ms 2388 KB Output is correct
21 Incorrect 50 ms 2452 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2392 KB Output is correct
2 Correct 57 ms 2388 KB Output is correct
3 Correct 54 ms 2384 KB Output is correct
4 Correct 50 ms 2388 KB Output is correct
5 Correct 48 ms 2456 KB Output is correct
6 Correct 63 ms 2356 KB Output is correct
7 Correct 50 ms 2384 KB Output is correct
8 Correct 53 ms 2580 KB Output is correct
9 Correct 56 ms 2536 KB Output is correct
10 Correct 50 ms 2524 KB Output is correct
11 Correct 51 ms 2388 KB Output is correct
12 Correct 50 ms 2384 KB Output is correct
13 Correct 54 ms 2568 KB Output is correct
14 Correct 50 ms 2392 KB Output is correct
15 Correct 51 ms 2432 KB Output is correct
16 Correct 51 ms 2380 KB Output is correct
17 Correct 58 ms 2432 KB Output is correct
18 Correct 61 ms 2564 KB Output is correct
19 Correct 170 ms 6792 KB Output is correct
20 Correct 191 ms 6536 KB Output is correct
21 Correct 154 ms 6508 KB Output is correct
22 Correct 128 ms 6140 KB Output is correct
23 Correct 80 ms 3408 KB Output is correct
24 Correct 79 ms 3488 KB Output is correct
25 Correct 137 ms 6788 KB Output is correct
26 Correct 137 ms 6792 KB Output is correct
27 Correct 154 ms 6592 KB Output is correct
28 Correct 164 ms 6672 KB Output is correct
29 Correct 173 ms 6524 KB Output is correct
30 Correct 90 ms 3444 KB Output is correct
31 Correct 160 ms 6668 KB Output is correct
32 Correct 174 ms 6384 KB Output is correct
33 Correct 80 ms 3416 KB Output is correct
34 Correct 154 ms 6608 KB Output is correct
35 Correct 116 ms 6056 KB Output is correct
36 Correct 89 ms 3484 KB Output is correct
37 Correct 80 ms 3332 KB Output is correct
38 Correct 164 ms 6536 KB Output is correct
39 Correct 126 ms 6784 KB Output is correct
40 Correct 113 ms 5388 KB Output is correct
41 Correct 188 ms 7000 KB Output is correct
42 Correct 95 ms 6076 KB Output is correct
43 Correct 54 ms 2440 KB Output is correct
44 Correct 64 ms 2388 KB Output is correct
45 Incorrect 50 ms 2452 KB Output isn't correct
46 Halted 0 ms 0 KB -