oj.uz

Submission #891306

# Submission time Handle Problem Language Result Execution time Memory
891306 2023-12-22T17:38:12 Z coldEr66 Crossing (JOI21_crossing) C++14
100 / 100
 932 ms 55296 KB 
#ifndef Yamada
#define Yamada
#include Yamada __FILE__ Yamada

char JOI[] = {'J', 'O', 'I'};

vector<int> cross(vector<int> &g1, vector<int> &g2) {
    vector<int> ret;
    for (int i = 0; i < SZ(g1); ++i) {
        int cur = 2 * (g1[i] + g2[i]) % 3;
        ret.eb(cur);
    }
    return ret;
}

const int maxn = 2e5 + 5;

struct node {
    int sc, tc, val, tag;
} seg[maxn * 4];

void build(int id, int l, int r, vector<int> &v, vector<int> &t) {
    seg[id].sc = seg[id].tc = seg[id].tag = -1;
    seg[id].val = 0;
    if (l == r-1) {
        seg[id].sc = v[l];
        seg[id].tc = t[l];
        seg[id].val = (v[l] == t[l]);
        seg[id].tag = -1;
        return;
    }
    int mid = l + r >> 1;
    build(id * 2 + 1, l, mid, v, t);
    build(id * 2 + 2, mid, r, v, t);
    seg[id].sc = (seg[id * 2 + 1].sc == seg[id * 2 + 2].sc ? seg[id * 2 + 1].sc : -1);
    seg[id].tc = (seg[id * 2 + 1].tc == seg[id * 2 + 2].tc ? seg[id * 2 + 1].tc : -1);
    seg[id].val = seg[id * 2 + 1].val & seg[id * 2 + 2].val;
}

void push(int id) {
    if (seg[id].tag == -1) return;
    seg[id * 2 + 1].tag = seg[id].tag;
    seg[id * 2 + 2].tag = seg[id].tag;
    seg[id].tag = -1;
}

void ins(int id, int l, int r, int L, int R, int op) {
    if (L == l && R == r) {
        seg[id].tag = op;
        seg[id].tc = op;
        seg[id].val = (seg[id].tc == seg[id].sc);
        return;
    }
    int mid = l + r >> 1;
    push(id);
    if (R <= mid) ins(id * 2 + 1, l, mid, L, R, op);
    else if (L >= mid) ins(id * 2 + 2, mid, r, L, R, op);
    else {
        ins(id * 2 + 1, l, mid, L, mid, op);
        ins(id * 2 + 2, mid, r, mid, R, op);
    }
    int lc = (seg[id * 2 + 1].tag == -1 ? seg[id * 2 + 1].tc : seg[id * 2 + 1].tag);
    int rc = (seg[id * 2 + 2].tag == -1 ? seg[id * 2 + 2].tc : seg[id * 2 + 2].tag);
    int lval = (seg[id * 2 + 1].tag == -1 ? seg[id * 2 + 1].val : (seg[id * 2 + 1].tag == seg[id * 2 + 1].sc));
    int rval = (seg[id * 2 + 2].tag == -1 ? seg[id * 2 + 2].val : (seg[id * 2 + 2].tag == seg[id * 2 + 2].sc));
    seg[id].tc = (lc == rc ? lc : -1);
    seg[id].val = lval & rval;
}

void solve() {
    int n; cin >> n;
    vector<int> gene[3];
    for (int i = 0; i < 3; ++i) {
        string s; cin >> s;
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < 3; ++k) {
                if (s[j] == JOI[k]) gene[i].eb(k);
            }
        }
    }
    vector<vector<int>> G;
    G.eb(gene[0]);
    G.eb(gene[1]);
    G.eb(gene[2]);
    vector<int> t1 = cross(gene[0], gene[1]);
    vector<int> t2 = cross(gene[0], gene[2]);
    vector<int> t3 = cross(gene[1], gene[2]);
    G.eb(t1);
    G.eb(t2);
    G.eb(t3);
    G.eb(cross(t1, gene[2]));
    G.eb(cross(t2, gene[1]));
    G.eb(cross(t3, gene[0]));
    int q; cin >> q;
    string T; cin >> T;
    vector<int> gt;
    for (int i = 0; i < n; ++i) {
        for (int k = 0; k < 3; ++k) {
            if (T[i] == JOI[k]) gt.eb(k);
        }
    }
    vector<pair<pii, int>> qr;
    for (int i = 1; i <= q; ++i) {
        int l, r;
        cin >> l >> r;
        --l;
        char c; cin >> c;
        int op = -1;
        for (int k = 0; k < 3; ++k) if (c == JOI[k]) op = k;
        qr.eb(pii(l, r), op);
    }

    vector<int> ans(q + 1);
    auto cal = [&](vector<int> &v) -> void {
        build(0, 0, n, v, gt);
        ans[0] |= seg[0].val;
        for (int i = 0; i < q; ++i){
            int l = qr[i].X.X, r = qr[i].X.Y, op = qr[i].Y;

            ins(0, 0, n, l, r, op);
            ans[i+1] |= seg[0].val;
        }
    };
    for (auto vec : G) {
        cal(vec);
    }
    for (int i = 0; i <= q; ++i) {
        if (ans[i]) print("Yes");
        else print("No");
    }
}

signed main() {
    IOS();
    int t = 1; // cin >> t;
    for (int i=1;i<=t;++i) solve();
    return 0;
}

#else

#ifdef local 
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize ("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define double __float80
using pii = pair<int, int>;
template <typename T> using MaxHeap = std::priority_queue<T>;
template <typename T> using MinHeap = std::priority_queue<T, vector<T>, greater<T>>;

#define SZ(a) ((int)(a).size())
#define ALL(a) begin(a), end(a)
#define RALL(a) rbegin(a), rend(a)
#define ee emplace
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define X first
#define Y second

#ifdef local
#define IOS() void()
#define debug(...) \
    fprintf(stderr, "\e[1;93m"), \
    fprintf(stderr, "At [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), \
    fprintf(stderr, "\e[0m")
template <typename T> void _do(T &&_t) {cerr << _t << '\n';}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#define print(...) \
    fprintf(stderr, "\e[1;96m"), \
    _P(__VA_ARGS__), \
    fprintf(stderr, "\e[0m")
#else
#define IOS() ios_base::sync_with_stdio(0); cin.tie(0)
#define debug(...) void()
#define print(...) _P(__VA_ARGS__)
#define endl '\n'
#endif

template <typename U, typename V> bool chmin(U &u, V v) {return u > v ? u = v, 1 : 0;}
template <typename U, typename V> bool chmax(U &u, V v) {return u < v ? u = v, 1 : 0;}

template <typename T> void _P(T &&_x) {cout << _x << '\n';}
template <typename T, typename ...S> void _P(T &&_x, S &&..._t) {cout << _x << " "; _P(_t...);}

#endif

Compilation message

Main.cpp: In function 'void build(int64_t, int64_t, int64_t, std::vector<long int>&, std::vector<long int>&)':
Main.cpp:32:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'void ins(int64_t, int64_t, int64_t, int64_t, int64_t, int64_t)':
Main.cpp:54:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 7884 KB Output is correct
2 Correct 238 ms 8396 KB Output is correct
3 Correct 192 ms 7968 KB Output is correct
4 Correct 182 ms 8372 KB Output is correct
5 Correct 176 ms 9400 KB Output is correct
6 Correct 183 ms 8976 KB Output is correct
7 Correct 182 ms 8880 KB Output is correct
8 Correct 190 ms 9032 KB Output is correct
9 Correct 196 ms 9412 KB Output is correct
10 Correct 194 ms 9416 KB Output is correct
11 Correct 203 ms 9144 KB Output is correct
12 Correct 193 ms 9424 KB Output is correct
13 Correct 200 ms 9396 KB Output is correct
14 Correct 197 ms 9156 KB Output is correct
15 Correct 205 ms 9496 KB Output is correct
16 Correct 193 ms 9164 KB Output is correct
17 Correct 202 ms 9680 KB Output is correct
18 Correct 167 ms 9676 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 7884 KB Output is correct
2 Correct 238 ms 8396 KB Output is correct
3 Correct 192 ms 7968 KB Output is correct
4 Correct 182 ms 8372 KB Output is correct
5 Correct 176 ms 9400 KB Output is correct
6 Correct 183 ms 8976 KB Output is correct
7 Correct 182 ms 8880 KB Output is correct
8 Correct 190 ms 9032 KB Output is correct
9 Correct 196 ms 9412 KB Output is correct
10 Correct 194 ms 9416 KB Output is correct
11 Correct 203 ms 9144 KB Output is correct
12 Correct 193 ms 9424 KB Output is correct
13 Correct 200 ms 9396 KB Output is correct
14 Correct 197 ms 9156 KB Output is correct
15 Correct 205 ms 9496 KB Output is correct
16 Correct 193 ms 9164 KB Output is correct
17 Correct 202 ms 9680 KB Output is correct
18 Correct 167 ms 9676 KB Output is correct
19 Correct 832 ms 54148 KB Output is correct
20 Correct 740 ms 53364 KB Output is correct
21 Correct 536 ms 51972 KB Output is correct
22 Correct 528 ms 48572 KB Output is correct
23 Correct 361 ms 13492 KB Output is correct
24 Correct 358 ms 12536 KB Output is correct
25 Correct 565 ms 53640 KB Output is correct
26 Correct 583 ms 54148 KB Output is correct
27 Correct 639 ms 54656 KB Output is correct
28 Correct 661 ms 55296 KB Output is correct
29 Correct 640 ms 52604 KB Output is correct
30 Correct 417 ms 13080 KB Output is correct
31 Correct 634 ms 53436 KB Output is correct
32 Correct 619 ms 50828 KB Output is correct
33 Correct 371 ms 13052 KB Output is correct
34 Correct 656 ms 53880 KB Output is correct
35 Correct 494 ms 46808 KB Output is correct
36 Correct 359 ms 12796 KB Output is correct
37 Correct 357 ms 13692 KB Output is correct
38 Correct 587 ms 53128 KB Output is correct
39 Correct 357 ms 54272 KB Output is correct
40 Correct 471 ms 36316 KB Output is correct
41 Correct 861 ms 54076 KB Output is correct
42 Correct 75 ms 54132 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 7884 KB Output is correct
2 Correct 238 ms 8396 KB Output is correct
3 Correct 192 ms 7968 KB Output is correct
4 Correct 182 ms 8372 KB Output is correct
5 Correct 176 ms 9400 KB Output is correct
6 Correct 183 ms 8976 KB Output is correct
7 Correct 182 ms 8880 KB Output is correct
8 Correct 190 ms 9032 KB Output is correct
9 Correct 196 ms 9412 KB Output is correct
10 Correct 194 ms 9416 KB Output is correct
11 Correct 203 ms 9144 KB Output is correct
12 Correct 193 ms 9424 KB Output is correct
13 Correct 200 ms 9396 KB Output is correct
14 Correct 197 ms 9156 KB Output is correct
15 Correct 205 ms 9496 KB Output is correct
16 Correct 193 ms 9164 KB Output is correct
17 Correct 202 ms 9680 KB Output is correct
18 Correct 167 ms 9676 KB Output is correct
19 Correct 231 ms 8908 KB Output is correct
20 Correct 203 ms 9140 KB Output is correct
21 Correct 193 ms 9680 KB Output is correct
22 Correct 166 ms 9164 KB Output is correct
23 Correct 191 ms 9072 KB Output is correct
24 Correct 189 ms 9392 KB Output is correct
25 Correct 202 ms 9380 KB Output is correct
26 Correct 177 ms 9344 KB Output is correct
27 Correct 192 ms 9308 KB Output is correct
28 Correct 177 ms 8748 KB Output is correct
29 Correct 198 ms 9912 KB Output is correct
30 Correct 167 ms 9420 KB Output is correct
31 Correct 200 ms 9916 KB Output is correct
32 Correct 192 ms 8652 KB Output is correct
33 Correct 197 ms 9156 KB Output is correct
34 Correct 178 ms 8896 KB Output is correct
35 Correct 193 ms 9192 KB Output is correct
36 Correct 197 ms 9168 KB Output is correct
37 Correct 198 ms 9292 KB Output is correct
38 Correct 199 ms 9912 KB Output is correct
39 Correct 193 ms 8656 KB Output is correct
40 Correct 205 ms 9416 KB Output is correct
41 Correct 193 ms 8640 KB Output is correct
42 Correct 198 ms 9420 KB Output is correct
43 Correct 185 ms 9640 KB Output is correct
44 Correct 198 ms 9168 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 7884 KB Output is correct
2 Correct 238 ms 8396 KB Output is correct
3 Correct 192 ms 7968 KB Output is correct
4 Correct 182 ms 8372 KB Output is correct
5 Correct 176 ms 9400 KB Output is correct
6 Correct 183 ms 8976 KB Output is correct
7 Correct 182 ms 8880 KB Output is correct
8 Correct 190 ms 9032 KB Output is correct
9 Correct 196 ms 9412 KB Output is correct
10 Correct 194 ms 9416 KB Output is correct
11 Correct 203 ms 9144 KB Output is correct
12 Correct 193 ms 9424 KB Output is correct
13 Correct 200 ms 9396 KB Output is correct
14 Correct 197 ms 9156 KB Output is correct
15 Correct 205 ms 9496 KB Output is correct
16 Correct 193 ms 9164 KB Output is correct
17 Correct 202 ms 9680 KB Output is correct
18 Correct 167 ms 9676 KB Output is correct
19 Correct 832 ms 54148 KB Output is correct
20 Correct 740 ms 53364 KB Output is correct
21 Correct 536 ms 51972 KB Output is correct
22 Correct 528 ms 48572 KB Output is correct
23 Correct 361 ms 13492 KB Output is correct
24 Correct 358 ms 12536 KB Output is correct
25 Correct 565 ms 53640 KB Output is correct
26 Correct 583 ms 54148 KB Output is correct
27 Correct 639 ms 54656 KB Output is correct
28 Correct 661 ms 55296 KB Output is correct
29 Correct 640 ms 52604 KB Output is correct
30 Correct 417 ms 13080 KB Output is correct
31 Correct 634 ms 53436 KB Output is correct
32 Correct 619 ms 50828 KB Output is correct
33 Correct 371 ms 13052 KB Output is correct
34 Correct 656 ms 53880 KB Output is correct
35 Correct 494 ms 46808 KB Output is correct
36 Correct 359 ms 12796 KB Output is correct
37 Correct 357 ms 13692 KB Output is correct
38 Correct 587 ms 53128 KB Output is correct
39 Correct 357 ms 54272 KB Output is correct
40 Correct 471 ms 36316 KB Output is correct
41 Correct 861 ms 54076 KB Output is correct
42 Correct 75 ms 54132 KB Output is correct
43 Correct 231 ms 8908 KB Output is correct
44 Correct 203 ms 9140 KB Output is correct
45 Correct 193 ms 9680 KB Output is correct
46 Correct 166 ms 9164 KB Output is correct
47 Correct 191 ms 9072 KB Output is correct
48 Correct 189 ms 9392 KB Output is correct
49 Correct 202 ms 9380 KB Output is correct
50 Correct 177 ms 9344 KB Output is correct
51 Correct 192 ms 9308 KB Output is correct
52 Correct 177 ms 8748 KB Output is correct
53 Correct 198 ms 9912 KB Output is correct
54 Correct 167 ms 9420 KB Output is correct
55 Correct 200 ms 9916 KB Output is correct
56 Correct 192 ms 8652 KB Output is correct
57 Correct 197 ms 9156 KB Output is correct
58 Correct 178 ms 8896 KB Output is correct
59 Correct 193 ms 9192 KB Output is correct
60 Correct 197 ms 9168 KB Output is correct
61 Correct 198 ms 9292 KB Output is correct
62 Correct 199 ms 9912 KB Output is correct
63 Correct 193 ms 8656 KB Output is correct
64 Correct 205 ms 9416 KB Output is correct
65 Correct 193 ms 8640 KB Output is correct
66 Correct 198 ms 9420 KB Output is correct
67 Correct 185 ms 9640 KB Output is correct
68 Correct 198 ms 9168 KB Output is correct
69 Correct 683 ms 49260 KB Output is correct
70 Correct 741 ms 53648 KB Output is correct
71 Correct 363 ms 12812 KB Output is correct
72 Correct 367 ms 13320 KB Output is correct
73 Correct 360 ms 12792 KB Output is correct
74 Correct 504 ms 49588 KB Output is correct
75 Correct 362 ms 12816 KB Output is correct
76 Correct 567 ms 53180 KB Output is correct
77 Correct 530 ms 48824 KB Output is correct
78 Correct 360 ms 13516 KB Output is correct
79 Correct 356 ms 13620 KB Output is correct
80 Correct 486 ms 45268 KB Output is correct
81 Correct 354 ms 13228 KB Output is correct
82 Correct 570 ms 53420 KB Output is correct
83 Correct 562 ms 51448 KB Output is correct
84 Correct 359 ms 14076 KB Output is correct
85 Correct 365 ms 13052 KB Output is correct
86 Correct 611 ms 47304 KB Output is correct
87 Correct 670 ms 54172 KB Output is correct
88 Correct 413 ms 12848 KB Output is correct
89 Correct 600 ms 50868 KB Output is correct
90 Correct 657 ms 54172 KB Output is correct
91 Correct 416 ms 13788 KB Output is correct
92 Correct 507 ms 47304 KB Output is correct
93 Correct 366 ms 14044 KB Output is correct
94 Correct 357 ms 13908 KB Output is correct
95 Correct 367 ms 13056 KB Output is correct
96 Correct 592 ms 54180 KB Output is correct
97 Correct 363 ms 54524 KB Output is correct
98 Correct 471 ms 35560 KB Output is correct
99 Correct 932 ms 53620 KB Output is correct
100 Correct 82 ms 53952 KB Output is correct