oj.uz

Submission #533170

# Submission time Handle Problem Language Result Execution time Memory
533170 2022-03-05T04:10:28 Z 4fecta Crossing (JOI21_crossing) C++17
100 / 100
 3247 ms 76652 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)
#define mid ((l + r) / 2)

const int MN = 200005;

int n, a[MN], d[MN], q, l[MN], r[MN], lzy[MN * 4], st[MN * 4][3][3], ans[MN];
char ch, t[MN];
vector<string> poss;
string x, y, z;

int g(char x) {
    if (x == 'J') return 0;
    if (x == 'O') return 1;
    return 2;
}

void push_down(int l, int r, int idx) {
    if (lzy[idx] == -1) return;
    for (int i = 0; i < 3; i++) {
        int cnt = 0;
        for (int j = 0; j < 3; j++) {
            cnt += st[idx][i][j];
            st[idx][i][j] = 0;
        }
        st[idx][i][lzy[idx]] = cnt;
    }
    if (l != r) lzy[idx * 2] = lzy[idx * 2 + 1] = lzy[idx];
    lzy[idx] = -1;
}

void build(int l, int r, int idx) {
    lzy[idx] = -1;
    if (l == r) {
        st[idx][a[l]][d[l]]++;
        return;
    }
    build(l, mid, idx * 2), build(mid + 1, r, idx * 2 + 1);
    for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) st[idx][i][j] = st[idx * 2][i][j] + st[idx * 2 + 1][i][j];
}

void upd(int l, int r, int x, int y, int val, int idx) {
    push_down(l, r, idx);
    if (r < x || l > y) return;
    if (r <= y && l >= x) {
        lzy[idx] = val;
        push_down(l, r, idx);
        return;
    }
    upd(l, mid, x, y, val, idx * 2), upd(mid + 1, r, x, y, val, idx * 2 + 1);
    for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) st[idx][i][j] = st[idx * 2][i][j] + st[idx * 2 + 1][i][j];
}

void check(int i) {
    if (st[1][0][0] + st[1][1][1] + st[1][2][2] == n) ans[i] = 1;
}

string c(string x, string y) {
    string ret;
    for (int i = 0; i < x.size(); i++) {
        if (x[i] == y[i]) ret += x[i];
        else {
            if (x[i] == 'J' && y[i] == 'O') ret += 'I';
            if (x[i] == 'O' && y[i] == 'J') ret += 'I';
            if (x[i] == 'I' && y[i] == 'O') ret += 'J';
            if (x[i] == 'O' && y[i] == 'I') ret += 'J';
            if (x[i] == 'J' && y[i] == 'I') ret += 'O';
            if (x[i] == 'I' && y[i] == 'J') ret += 'O';
        }
    }
    return ret;
}

int32_t main() {
    boost();

    cin >> n >> x >> y >> z;
    poss.push_back(x);
    poss.push_back(y);
    poss.push_back(z);
    poss.push_back(c(x, y));
    poss.push_back(c(x, z));
    poss.push_back(c(y, z));
    poss.push_back(c(c(x, y), z));
    poss.push_back(c(c(x, z), y));
    poss.push_back(c(c(y, z), x));
    cin >> q;
    for (int i = 1; i <= n; i++) {
        cin >> ch;
        d[i] = g(ch);
    }
    for (int i = 1; i <= q; i++) cin >> l[i] >> r[i] >> t[i];
    for (string s : poss) {
        memset(st, 0, sizeof(st));
        for (int i = 1; i <= n; i++) a[i] = g(s[i - 1]);
        build(1, n, 1);
        check(0);
        for (int i = 1; i <= q; i++) {
            int val = g(t[i]);
            upd(1, n, l[i], r[i], val, 1);
            check(i);
        }
    }
    for (int i = 0; i <= q; i++) {
        if (ans[i]) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}

Compilation message

Main.cpp: In function 'std::string c(std::string, std::string)':
Main.cpp:67:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < x.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 60312 KB Output is correct
2 Correct 548 ms 60532 KB Output is correct
3 Correct 609 ms 60572 KB Output is correct
4 Correct 453 ms 62076 KB Output is correct
5 Correct 444 ms 61936 KB Output is correct
6 Correct 461 ms 61848 KB Output is correct
7 Correct 476 ms 62164 KB Output is correct
8 Correct 476 ms 62092 KB Output is correct
9 Correct 482 ms 62084 KB Output is correct
10 Correct 467 ms 60536 KB Output is correct
11 Correct 482 ms 60532 KB Output is correct
12 Correct 484 ms 60612 KB Output is correct
13 Correct 550 ms 60532 KB Output is correct
14 Correct 478 ms 60536 KB Output is correct
15 Correct 565 ms 60536 KB Output is correct
16 Correct 457 ms 60612 KB Output is correct
17 Correct 478 ms 60588 KB Output is correct
18 Correct 531 ms 62092 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 60312 KB Output is correct
2 Correct 548 ms 60532 KB Output is correct
3 Correct 609 ms 60572 KB Output is correct
4 Correct 453 ms 62076 KB Output is correct
5 Correct 444 ms 61936 KB Output is correct
6 Correct 461 ms 61848 KB Output is correct
7 Correct 476 ms 62164 KB Output is correct
8 Correct 476 ms 62092 KB Output is correct
9 Correct 482 ms 62084 KB Output is correct
10 Correct 467 ms 60536 KB Output is correct
11 Correct 482 ms 60532 KB Output is correct
12 Correct 484 ms 60612 KB Output is correct
13 Correct 550 ms 60532 KB Output is correct
14 Correct 478 ms 60536 KB Output is correct
15 Correct 565 ms 60536 KB Output is correct
16 Correct 457 ms 60612 KB Output is correct
17 Correct 478 ms 60588 KB Output is correct
18 Correct 531 ms 62092 KB Output is correct
19 Correct 2850 ms 71140 KB Output is correct
20 Correct 2261 ms 71144 KB Output is correct
21 Correct 1694 ms 70636 KB Output is correct
22 Correct 1582 ms 69984 KB Output is correct
23 Correct 907 ms 61296 KB Output is correct
24 Correct 888 ms 61248 KB Output is correct
25 Correct 1838 ms 71156 KB Output is correct
26 Correct 1818 ms 71152 KB Output is correct
27 Correct 2104 ms 71308 KB Output is correct
28 Correct 2163 ms 71316 KB Output is correct
29 Correct 1822 ms 71152 KB Output is correct
30 Correct 1010 ms 61540 KB Output is correct
31 Correct 1961 ms 71280 KB Output is correct
32 Correct 2011 ms 70592 KB Output is correct
33 Correct 899 ms 61260 KB Output is correct
34 Correct 2047 ms 71204 KB Output is correct
35 Correct 1495 ms 69384 KB Output is correct
36 Correct 887 ms 61168 KB Output is correct
37 Correct 833 ms 61252 KB Output is correct
38 Correct 1838 ms 72708 KB Output is correct
39 Correct 929 ms 72704 KB Output is correct
40 Correct 1613 ms 66980 KB Output is correct
41 Correct 3247 ms 72964 KB Output is correct
42 Correct 179 ms 72964 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 60312 KB Output is correct
2 Correct 548 ms 60532 KB Output is correct
3 Correct 609 ms 60572 KB Output is correct
4 Correct 453 ms 62076 KB Output is correct
5 Correct 444 ms 61936 KB Output is correct
6 Correct 461 ms 61848 KB Output is correct
7 Correct 476 ms 62164 KB Output is correct
8 Correct 476 ms 62092 KB Output is correct
9 Correct 482 ms 62084 KB Output is correct
10 Correct 467 ms 60536 KB Output is correct
11 Correct 482 ms 60532 KB Output is correct
12 Correct 484 ms 60612 KB Output is correct
13 Correct 550 ms 60532 KB Output is correct
14 Correct 478 ms 60536 KB Output is correct
15 Correct 565 ms 60536 KB Output is correct
16 Correct 457 ms 60612 KB Output is correct
17 Correct 478 ms 60588 KB Output is correct
18 Correct 531 ms 62092 KB Output is correct
19 Correct 591 ms 60404 KB Output is correct
20 Correct 630 ms 60536 KB Output is correct
21 Correct 465 ms 62092 KB Output is correct
22 Correct 414 ms 63156 KB Output is correct
23 Correct 490 ms 63644 KB Output is correct
24 Correct 461 ms 63436 KB Output is correct
25 Correct 484 ms 63620 KB Output is correct
26 Correct 436 ms 63468 KB Output is correct
27 Correct 463 ms 63660 KB Output is correct
28 Correct 467 ms 63072 KB Output is correct
29 Correct 496 ms 63744 KB Output is correct
30 Correct 410 ms 63148 KB Output is correct
31 Correct 479 ms 63704 KB Output is correct
32 Correct 461 ms 63564 KB Output is correct
33 Correct 475 ms 63664 KB Output is correct
34 Correct 477 ms 63332 KB Output is correct
35 Correct 477 ms 62068 KB Output is correct
36 Correct 478 ms 62072 KB Output is correct
37 Correct 477 ms 62068 KB Output is correct
38 Correct 472 ms 62136 KB Output is correct
39 Correct 484 ms 62068 KB Output is correct
40 Correct 512 ms 62116 KB Output is correct
41 Correct 476 ms 62064 KB Output is correct
42 Correct 476 ms 62148 KB Output is correct
43 Correct 435 ms 63652 KB Output is correct
44 Correct 483 ms 63692 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 60312 KB Output is correct
2 Correct 548 ms 60532 KB Output is correct
3 Correct 609 ms 60572 KB Output is correct
4 Correct 453 ms 62076 KB Output is correct
5 Correct 444 ms 61936 KB Output is correct
6 Correct 461 ms 61848 KB Output is correct
7 Correct 476 ms 62164 KB Output is correct
8 Correct 476 ms 62092 KB Output is correct
9 Correct 482 ms 62084 KB Output is correct
10 Correct 467 ms 60536 KB Output is correct
11 Correct 482 ms 60532 KB Output is correct
12 Correct 484 ms 60612 KB Output is correct
13 Correct 550 ms 60532 KB Output is correct
14 Correct 478 ms 60536 KB Output is correct
15 Correct 565 ms 60536 KB Output is correct
16 Correct 457 ms 60612 KB Output is correct
17 Correct 478 ms 60588 KB Output is correct
18 Correct 531 ms 62092 KB Output is correct
19 Correct 2850 ms 71140 KB Output is correct
20 Correct 2261 ms 71144 KB Output is correct
21 Correct 1694 ms 70636 KB Output is correct
22 Correct 1582 ms 69984 KB Output is correct
23 Correct 907 ms 61296 KB Output is correct
24 Correct 888 ms 61248 KB Output is correct
25 Correct 1838 ms 71156 KB Output is correct
26 Correct 1818 ms 71152 KB Output is correct
27 Correct 2104 ms 71308 KB Output is correct
28 Correct 2163 ms 71316 KB Output is correct
29 Correct 1822 ms 71152 KB Output is correct
30 Correct 1010 ms 61540 KB Output is correct
31 Correct 1961 ms 71280 KB Output is correct
32 Correct 2011 ms 70592 KB Output is correct
33 Correct 899 ms 61260 KB Output is correct
34 Correct 2047 ms 71204 KB Output is correct
35 Correct 1495 ms 69384 KB Output is correct
36 Correct 887 ms 61168 KB Output is correct
37 Correct 833 ms 61252 KB Output is correct
38 Correct 1838 ms 72708 KB Output is correct
39 Correct 929 ms 72704 KB Output is correct
40 Correct 1613 ms 66980 KB Output is correct
41 Correct 3247 ms 72964 KB Output is correct
42 Correct 179 ms 72964 KB Output is correct
43 Correct 591 ms 60404 KB Output is correct
44 Correct 630 ms 60536 KB Output is correct
45 Correct 465 ms 62092 KB Output is correct
46 Correct 414 ms 63156 KB Output is correct
47 Correct 490 ms 63644 KB Output is correct
48 Correct 461 ms 63436 KB Output is correct
49 Correct 484 ms 63620 KB Output is correct
50 Correct 436 ms 63468 KB Output is correct
51 Correct 463 ms 63660 KB Output is correct
52 Correct 467 ms 63072 KB Output is correct
53 Correct 496 ms 63744 KB Output is correct
54 Correct 410 ms 63148 KB Output is correct
55 Correct 479 ms 63704 KB Output is correct
56 Correct 461 ms 63564 KB Output is correct
57 Correct 475 ms 63664 KB Output is correct
58 Correct 477 ms 63332 KB Output is correct
59 Correct 477 ms 62068 KB Output is correct
60 Correct 478 ms 62072 KB Output is correct
61 Correct 477 ms 62068 KB Output is correct
62 Correct 472 ms 62136 KB Output is correct
63 Correct 484 ms 62068 KB Output is correct
64 Correct 512 ms 62116 KB Output is correct
65 Correct 476 ms 62064 KB Output is correct
66 Correct 476 ms 62148 KB Output is correct
67 Correct 435 ms 63652 KB Output is correct
68 Correct 483 ms 63692 KB Output is correct
69 Correct 2539 ms 73120 KB Output is correct
70 Correct 2252 ms 74812 KB Output is correct
71 Correct 852 ms 63692 KB Output is correct
72 Correct 874 ms 63680 KB Output is correct
73 Correct 865 ms 63688 KB Output is correct
74 Correct 1571 ms 73168 KB Output is correct
75 Correct 874 ms 63600 KB Output is correct
76 Correct 1811 ms 74844 KB Output is correct
77 Correct 1780 ms 73396 KB Output is correct
78 Correct 876 ms 63684 KB Output is correct
79 Correct 945 ms 63628 KB Output is correct
80 Correct 1523 ms 72360 KB Output is correct
81 Correct 834 ms 63576 KB Output is correct
82 Correct 1818 ms 74960 KB Output is correct
83 Correct 1820 ms 74196 KB Output is correct
84 Correct 887 ms 63532 KB Output is correct
85 Correct 964 ms 63540 KB Output is correct
86 Correct 1976 ms 72976 KB Output is correct
87 Correct 2075 ms 74972 KB Output is correct
88 Correct 1006 ms 63764 KB Output is correct
89 Correct 2012 ms 73612 KB Output is correct
90 Correct 2027 ms 74896 KB Output is correct
91 Correct 945 ms 63676 KB Output is correct
92 Correct 1492 ms 72632 KB Output is correct
93 Correct 917 ms 63504 KB Output is correct
94 Correct 853 ms 63500 KB Output is correct
95 Correct 899 ms 63840 KB Output is correct
96 Correct 1749 ms 76168 KB Output is correct
97 Correct 918 ms 76432 KB Output is correct
98 Correct 1489 ms 70292 KB Output is correct
99 Correct 2969 ms 76652 KB Output is correct
100 Correct 197 ms 75924 KB Output is correct