oj.uz

Submission #891256

# Submission time Handle Problem Language Result Execution time Memory
891256 2023-12-22T15:28:20 Z lolicon Crossing (JOI21_crossing) C++14
100 / 100
 2733 ms 295220 KB 
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
using namespace std;

const int maxn = 2e5 + 5;

void transform(int A[], int B[], int C[], int sz) {
    for(int i = 0; i < sz; ++i) {
        if(A[i] == B[i]) C[i] = A[i];
        else {
            C[i] = 3 - A[i] - B[i];
        }
    }
}

int get(char c) {
    if(c == 'J') return 0;
    if(c == 'O') return 1;
    if(c == 'I') return 2;
    return -1;
}

struct SGT {
    struct node {
        int cnt[3][3], tag;
    };
    vector<node> tr;
    SGT(int sz) : tr(sz << 2) {}
    void pull(int x) {
        for(int i = 0; i < 3; ++i) {
            for(int j = 0; j < 3; ++j)
                tr[x].cnt[i][j] = tr[(x << 1)].cnt[i][j] + tr[(x << 1) | 1].cnt[i][j];
        }
    }
    void print(int x) {
        for(int i = 0; i < 3; ++i) {
            for(int j = 0; j < 3; ++j) {
                printf("%d%c", tr[x].cnt[i][j], " \n"[j == 2]);
            }
        }
    } 
    void apply(int x, int color) {
        for(int i = 0; i < 3; ++i) {
            int sum = 0;
            for(int j = 0; j < 3; ++j) {
                sum += tr[x].cnt[i][j];
            }
            for(int j = 0; j < 3; ++j) {
                tr[x].cnt[i][j] = 0;
            }
            tr[x].cnt[i][color] = sum;
        }
    }
    void push(int x) {
        if(tr[x].tag != -1) {
            // apply
            apply(x << 1, tr[x].tag);
            apply((x << 1) | 1, tr[x].tag);
            
            // set tag
            tr[x << 1].tag = tr[x].tag;
            tr[(x << 1) | 1].tag = tr[x].tag;
            tr[x].tag = -1;
            // printf("pushed %d: \n", x << 1);
            // print(x << 1);
            // printf("pushed %d: \n", (x << 1) | 1);
            // print((x << 1) | 1);
        }
    }
    void build(int x, int L, int R, int ori[], int arr[]) {
        tr[x].tag = -1;
        if(L == R) {
            memset(tr[x].cnt, 0, sizeof(int)*9);
            tr[x].cnt[ori[L]][arr[L]]++;
            // printf("build %d: \n", x);
            // print(x);
            return;
        }
        int mid = (L + R) >> 1;
        build(x << 1, L, mid, ori, arr);
        build((x << 1) | 1, mid + 1, R, ori, arr);
        pull(x);
        // printf("build %d: \n", x);
        // print(x);
    }
    void upd(int x, int L, int R, int l, int r, int color) {
        // printf("upd [%d, %d], %d, at [%d %d]\n", l, r, color, L, R);
        if(l <= L && R <= r) {
            apply(x, color);
            tr[x].tag = color;
            // printf("upded [%d, %d], %d, at [%d %d]\n", l, r, color, L, R);
            // print(x);
            return;
        }
        push(x);
        int mid = (L + R) >> 1;
        if(l <= mid) upd(x << 1, L, mid, l, r, color);
        if(r > mid) upd((x << 1) | 1, mid + 1, R, l, r, color);
        pull(x);
        // printf("upded [%d, %d], %d, at [%d %d]\n", l, r, color, L, R);
        // print(x);
    }
    int ask() {
        int ret = 0;
        for(int i = 0; i < 3; ++i) {
            ret += tr[1].cnt[i][i];
        }
        return ret;
    }
};

int S[9][maxn], T[maxn];
vector<SGT> loli;
int n, q;

void upd(int l, int r, int c) {
    for(auto &it : loli) {
        it.upd(1, 0, n - 1, l, r, c);
    }
}

bool chk() {
    for(auto &it : loli) {
        if(it.ask() == n) return true;
    }
    return false;
}

void print(int A[]) {
    for(int i = 0; i < n; ++i) 
        printf("%d%c", A[i], " \n"[i == n - 1]);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for(int i = 0; i < 3; ++i) {
        string s; cin >> s;
        for(int j = 0; j < n; ++j) S[i][j] = get(s[j]);
    }
    cin >> q;
    string t; cin >> t;
    for(int i = 0; i < n; ++i) T[i] = get(t[i]);
    // print(T);
    // build tree
    transform(S[0], S[1], S[3], n);
    transform(S[0], S[2], S[4], n);
    transform(S[1], S[2], S[5], n);
    transform(S[3], S[4], S[6], n);
    transform(S[3], S[5], S[7], n);
    transform(S[4], S[5], S[8], n);
    for(int i = 0; i < 9; ++i) {
        // print(S[i]);
        loli.emplace_back(n);
        loli.back().build(1, 0, n - 1, S[i], T);
    }
    // solve
    cout << (chk() ? "Yes" : "No") << '\n';
    for(int i = 0; i < q; ++i) {
        int l, r, c; char _c;
        cin >> l >> r >> _c; c = get(_c); l--, r--;
        upd(l, r, c);
        cout << (chk() ? "Yes" : "No") << '\n';
    } 
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 7256 KB Output is correct
2 Correct 286 ms 7124 KB Output is correct
3 Correct 344 ms 7296 KB Output is correct
4 Correct 215 ms 7252 KB Output is correct
5 Correct 216 ms 7244 KB Output is correct
6 Correct 230 ms 7208 KB Output is correct
7 Correct 217 ms 7284 KB Output is correct
8 Correct 274 ms 7248 KB Output is correct
9 Correct 234 ms 7248 KB Output is correct
10 Correct 233 ms 7180 KB Output is correct
11 Correct 250 ms 7320 KB Output is correct
12 Correct 230 ms 7320 KB Output is correct
13 Correct 235 ms 7252 KB Output is correct
14 Correct 228 ms 7368 KB Output is correct
15 Correct 234 ms 7312 KB Output is correct
16 Correct 242 ms 7544 KB Output is correct
17 Correct 240 ms 7252 KB Output is correct
18 Correct 299 ms 7252 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 7256 KB Output is correct
2 Correct 286 ms 7124 KB Output is correct
3 Correct 344 ms 7296 KB Output is correct
4 Correct 215 ms 7252 KB Output is correct
5 Correct 216 ms 7244 KB Output is correct
6 Correct 230 ms 7208 KB Output is correct
7 Correct 217 ms 7284 KB Output is correct
8 Correct 274 ms 7248 KB Output is correct
9 Correct 234 ms 7248 KB Output is correct
10 Correct 233 ms 7180 KB Output is correct
11 Correct 250 ms 7320 KB Output is correct
12 Correct 230 ms 7320 KB Output is correct
13 Correct 235 ms 7252 KB Output is correct
14 Correct 228 ms 7368 KB Output is correct
15 Correct 234 ms 7312 KB Output is correct
16 Correct 242 ms 7544 KB Output is correct
17 Correct 240 ms 7252 KB Output is correct
18 Correct 299 ms 7252 KB Output is correct
19 Correct 2474 ms 291108 KB Output is correct
20 Correct 1982 ms 291176 KB Output is correct
21 Correct 1311 ms 276540 KB Output is correct
22 Correct 1366 ms 249228 KB Output is correct
23 Correct 517 ms 23368 KB Output is correct
24 Correct 556 ms 23356 KB Output is correct
25 Correct 1260 ms 293168 KB Output is correct
26 Correct 1438 ms 293236 KB Output is correct
27 Correct 1698 ms 293376 KB Output is correct
28 Correct 1768 ms 293260 KB Output is correct
29 Correct 1515 ms 285252 KB Output is correct
30 Correct 582 ms 23824 KB Output is correct
31 Correct 1653 ms 293592 KB Output is correct
32 Correct 1597 ms 267968 KB Output is correct
33 Correct 541 ms 22896 KB Output is correct
34 Correct 1680 ms 293508 KB Output is correct
35 Correct 1086 ms 220460 KB Output is correct
36 Correct 520 ms 23380 KB Output is correct
37 Correct 530 ms 23092 KB Output is correct
38 Correct 1566 ms 293188 KB Output is correct
39 Correct 567 ms 293172 KB Output is correct
40 Correct 1238 ms 195672 KB Output is correct
41 Correct 2733 ms 293804 KB Output is correct
42 Correct 123 ms 292916 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 7256 KB Output is correct
2 Correct 286 ms 7124 KB Output is correct
3 Correct 344 ms 7296 KB Output is correct
4 Correct 215 ms 7252 KB Output is correct
5 Correct 216 ms 7244 KB Output is correct
6 Correct 230 ms 7208 KB Output is correct
7 Correct 217 ms 7284 KB Output is correct
8 Correct 274 ms 7248 KB Output is correct
9 Correct 234 ms 7248 KB Output is correct
10 Correct 233 ms 7180 KB Output is correct
11 Correct 250 ms 7320 KB Output is correct
12 Correct 230 ms 7320 KB Output is correct
13 Correct 235 ms 7252 KB Output is correct
14 Correct 228 ms 7368 KB Output is correct
15 Correct 234 ms 7312 KB Output is correct
16 Correct 242 ms 7544 KB Output is correct
17 Correct 240 ms 7252 KB Output is correct
18 Correct 299 ms 7252 KB Output is correct
19 Correct 275 ms 8272 KB Output is correct
20 Correct 347 ms 8272 KB Output is correct
21 Correct 235 ms 8128 KB Output is correct
22 Correct 196 ms 8612 KB Output is correct
23 Correct 228 ms 8788 KB Output is correct
24 Correct 222 ms 8700 KB Output is correct
25 Correct 250 ms 8788 KB Output is correct
26 Correct 221 ms 8784 KB Output is correct
27 Correct 233 ms 9044 KB Output is correct
28 Correct 214 ms 8488 KB Output is correct
29 Correct 232 ms 8788 KB Output is correct
30 Correct 203 ms 8784 KB Output is correct
31 Correct 231 ms 8788 KB Output is correct
32 Correct 227 ms 8644 KB Output is correct
33 Correct 234 ms 8700 KB Output is correct
34 Correct 205 ms 8656 KB Output is correct
35 Correct 236 ms 9048 KB Output is correct
36 Correct 235 ms 8784 KB Output is correct
37 Correct 230 ms 8796 KB Output is correct
38 Correct 235 ms 8744 KB Output is correct
39 Correct 233 ms 8696 KB Output is correct
40 Correct 240 ms 8808 KB Output is correct
41 Correct 235 ms 8880 KB Output is correct
42 Correct 237 ms 8788 KB Output is correct
43 Correct 227 ms 8788 KB Output is correct
44 Correct 234 ms 8644 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 7256 KB Output is correct
2 Correct 286 ms 7124 KB Output is correct
3 Correct 344 ms 7296 KB Output is correct
4 Correct 215 ms 7252 KB Output is correct
5 Correct 216 ms 7244 KB Output is correct
6 Correct 230 ms 7208 KB Output is correct
7 Correct 217 ms 7284 KB Output is correct
8 Correct 274 ms 7248 KB Output is correct
9 Correct 234 ms 7248 KB Output is correct
10 Correct 233 ms 7180 KB Output is correct
11 Correct 250 ms 7320 KB Output is correct
12 Correct 230 ms 7320 KB Output is correct
13 Correct 235 ms 7252 KB Output is correct
14 Correct 228 ms 7368 KB Output is correct
15 Correct 234 ms 7312 KB Output is correct
16 Correct 242 ms 7544 KB Output is correct
17 Correct 240 ms 7252 KB Output is correct
18 Correct 299 ms 7252 KB Output is correct
19 Correct 2474 ms 291108 KB Output is correct
20 Correct 1982 ms 291176 KB Output is correct
21 Correct 1311 ms 276540 KB Output is correct
22 Correct 1366 ms 249228 KB Output is correct
23 Correct 517 ms 23368 KB Output is correct
24 Correct 556 ms 23356 KB Output is correct
25 Correct 1260 ms 293168 KB Output is correct
26 Correct 1438 ms 293236 KB Output is correct
27 Correct 1698 ms 293376 KB Output is correct
28 Correct 1768 ms 293260 KB Output is correct
29 Correct 1515 ms 285252 KB Output is correct
30 Correct 582 ms 23824 KB Output is correct
31 Correct 1653 ms 293592 KB Output is correct
32 Correct 1597 ms 267968 KB Output is correct
33 Correct 541 ms 22896 KB Output is correct
34 Correct 1680 ms 293508 KB Output is correct
35 Correct 1086 ms 220460 KB Output is correct
36 Correct 520 ms 23380 KB Output is correct
37 Correct 530 ms 23092 KB Output is correct
38 Correct 1566 ms 293188 KB Output is correct
39 Correct 567 ms 293172 KB Output is correct
40 Correct 1238 ms 195672 KB Output is correct
41 Correct 2733 ms 293804 KB Output is correct
42 Correct 123 ms 292916 KB Output is correct
43 Correct 275 ms 8272 KB Output is correct
44 Correct 347 ms 8272 KB Output is correct
45 Correct 235 ms 8128 KB Output is correct
46 Correct 196 ms 8612 KB Output is correct
47 Correct 228 ms 8788 KB Output is correct
48 Correct 222 ms 8700 KB Output is correct
49 Correct 250 ms 8788 KB Output is correct
50 Correct 221 ms 8784 KB Output is correct
51 Correct 233 ms 9044 KB Output is correct
52 Correct 214 ms 8488 KB Output is correct
53 Correct 232 ms 8788 KB Output is correct
54 Correct 203 ms 8784 KB Output is correct
55 Correct 231 ms 8788 KB Output is correct
56 Correct 227 ms 8644 KB Output is correct
57 Correct 234 ms 8700 KB Output is correct
58 Correct 205 ms 8656 KB Output is correct
59 Correct 236 ms 9048 KB Output is correct
60 Correct 235 ms 8784 KB Output is correct
61 Correct 230 ms 8796 KB Output is correct
62 Correct 235 ms 8744 KB Output is correct
63 Correct 233 ms 8696 KB Output is correct
64 Correct 240 ms 8808 KB Output is correct
65 Correct 235 ms 8880 KB Output is correct
66 Correct 237 ms 8788 KB Output is correct
67 Correct 227 ms 8788 KB Output is correct
68 Correct 234 ms 8644 KB Output is correct
69 Correct 1967 ms 248276 KB Output is correct
70 Correct 1762 ms 294700 KB Output is correct
71 Correct 525 ms 24252 KB Output is correct
72 Correct 567 ms 24332 KB Output is correct
73 Correct 626 ms 24404 KB Output is correct
74 Correct 1127 ms 247432 KB Output is correct
75 Correct 523 ms 23888 KB Output is correct
76 Correct 1220 ms 295000 KB Output is correct
77 Correct 1318 ms 247660 KB Output is correct
78 Correct 509 ms 23944 KB Output is correct
79 Correct 548 ms 24148 KB Output is correct
80 Correct 1178 ms 212364 KB Output is correct
81 Correct 518 ms 23912 KB Output is correct
82 Correct 1208 ms 294620 KB Output is correct
83 Correct 1252 ms 277628 KB Output is correct
84 Correct 567 ms 23760 KB Output is correct
85 Correct 495 ms 23716 KB Output is correct
86 Correct 1634 ms 226464 KB Output is correct
87 Correct 1680 ms 294784 KB Output is correct
88 Correct 601 ms 24664 KB Output is correct
89 Correct 1362 ms 260956 KB Output is correct
90 Correct 1506 ms 294960 KB Output is correct
91 Correct 572 ms 23936 KB Output is correct
92 Correct 1039 ms 222808 KB Output is correct
93 Correct 525 ms 23792 KB Output is correct
94 Correct 494 ms 23632 KB Output is correct
95 Correct 519 ms 23892 KB Output is correct
96 Correct 1717 ms 294516 KB Output is correct
97 Correct 610 ms 294836 KB Output is correct
98 Correct 1175 ms 196744 KB Output is correct
99 Correct 2626 ms 295220 KB Output is correct
100 Correct 138 ms 294112 KB Output is correct