oj.uz

Submission #533808

# Submission time Handle Problem Language Result Execution time Memory
533808 2022-03-07T10:33:14 Z RaresFelix Crossing (JOI21_crossing) C++17
26 / 100
 1746 ms 82288 KB 
#include <bits/stdc++.h>

using namespace std;

#define LT(x) ((x) == 'I' ? 2 : (x) == 'O')
#define CMB(x, y) ((x) == (y) ? (x) : 3 - ((x) + (y)))
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define MN 207171
int n, q;
vector<int> C[9], P;
struct SL {
    vector<int> B;
    int Vl[4 * MN], Eq[4 * MN], Lz[4 * MN];
    void bld(int u, int s, int d) {
        if(s == d) {
            Vl[u] = B[s];
            Eq[u] = (B[s] == P[s]);
            return;
        }
        bld(u * 2, s, (s + d) / 2);
        bld(u * 2 + 1, (s + d) / 2 + 1, d);
        Vl[u] = (Vl[u * 2] == Vl[u * 2 + 1] ? Vl[u * 2] : -1);
        Eq[u] = Eq[u * 2] && Eq[u * 2 + 1];
    }
    SL(vector<int> B) : B(std::move(B)){
        bld(1, 0, n-1);
    }
    void prp(int u, int s, int d) {
        if(!Lz[u]) return;
        int v = Lz[u] - 3;
        Eq[u] = (Vl[u] == v);
        if(s != d)
            Lz[u * 2] = Lz[u * 2 + 1] = Lz[u];
        Lz[u] = 0;
    }
    void pset(int l, int r, int v, int u, int s, int d) {
        prp(u, s, d);
        if(r < s || d < l) return;
        if(l <= s && d <= r) {
            Lz[u] = v + 3;
            prp(u, s, d);
            return;
        }
        pset(l, r, v, u * 2, s, (s + d) / 2);
        pset(l, r, v, u * 2 + 1, (s + d) / 2 + 1, d);
        Vl[u] = (Vl[u * 2] == Vl[u * 2 + 1] ? Vl[u * 2] : -1);
        Eq[u] = Eq[u * 2] && Eq[u * 2 + 1];
    }
};
vector<SL> SS;
void af() {
    int ok = 0;
    for(auto &it : SS) ok |= it.Eq[1];
    cout << (ok ? "Yes\n" : "No\n");
}
void rd(vi &C) {
    string w;
    cin >> w;
    for(auto it : w) C.push_back(LT(it));
}
int main() {
    cin >> n;
    for(int i = 0; i < 3; ++i) rd(C[i]);
    int nr = 2;
    for(int i = 0; i < 3; ++i)
        for(int j = i + 1; j < 3; ++j)
            for(int k = !(++nr); k < n; ++k) C[nr].push_back(CMB(C[i][k], C[j][k]));
    for(int i = 0; i < n; ++i) C[6].push_back(CMB(C[0][i], CMB(C[1][i], C[2][i])));
    cin >> q;
    rd(P);
    for(int i = 0; i < 7; ++i)
        SS.emplace_back(C[i]);
    af();
    for(int i = 1, l, r; i <= q; ++i) {
        char c;
        cin >> l >> r >> c;
        --l, --r;
        for(auto &it : SS)
            it.pset(l, r, LT(c), 1, 0, n - 1);
        af();
    }
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 58800 KB Output is correct
2 Correct 525 ms 58792 KB Output is correct
3 Correct 517 ms 58804 KB Output is correct
4 Correct 472 ms 58820 KB Output is correct
5 Correct 465 ms 58740 KB Output is correct
6 Correct 474 ms 58828 KB Output is correct
7 Correct 492 ms 58800 KB Output is correct
8 Correct 518 ms 58720 KB Output is correct
9 Correct 483 ms 58800 KB Output is correct
10 Correct 491 ms 58820 KB Output is correct
11 Correct 483 ms 58820 KB Output is correct
12 Correct 480 ms 58720 KB Output is correct
13 Correct 487 ms 58796 KB Output is correct
14 Correct 481 ms 58820 KB Output is correct
15 Correct 503 ms 58936 KB Output is correct
16 Correct 499 ms 58820 KB Output is correct
17 Correct 491 ms 58800 KB Output is correct
18 Correct 499 ms 58892 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 58800 KB Output is correct
2 Correct 525 ms 58792 KB Output is correct
3 Correct 517 ms 58804 KB Output is correct
4 Correct 472 ms 58820 KB Output is correct
5 Correct 465 ms 58740 KB Output is correct
6 Correct 474 ms 58828 KB Output is correct
7 Correct 492 ms 58800 KB Output is correct
8 Correct 518 ms 58720 KB Output is correct
9 Correct 483 ms 58800 KB Output is correct
10 Correct 491 ms 58820 KB Output is correct
11 Correct 483 ms 58820 KB Output is correct
12 Correct 480 ms 58720 KB Output is correct
13 Correct 487 ms 58796 KB Output is correct
14 Correct 481 ms 58820 KB Output is correct
15 Correct 503 ms 58936 KB Output is correct
16 Correct 499 ms 58820 KB Output is correct
17 Correct 491 ms 58800 KB Output is correct
18 Correct 499 ms 58892 KB Output is correct
19 Correct 1651 ms 82288 KB Output is correct
20 Correct 1329 ms 82276 KB Output is correct
21 Correct 1243 ms 81468 KB Output is correct
22 Correct 1146 ms 80420 KB Output is correct
23 Correct 742 ms 60232 KB Output is correct
24 Correct 778 ms 60176 KB Output is correct
25 Correct 1322 ms 82272 KB Output is correct
26 Correct 1295 ms 82196 KB Output is correct
27 Correct 1406 ms 82208 KB Output is correct
28 Correct 1386 ms 82280 KB Output is correct
29 Correct 1362 ms 82116 KB Output is correct
30 Correct 757 ms 60236 KB Output is correct
31 Correct 1382 ms 82216 KB Output is correct
32 Correct 1315 ms 81392 KB Output is correct
33 Correct 719 ms 60164 KB Output is correct
34 Correct 1379 ms 82284 KB Output is correct
35 Correct 1096 ms 79376 KB Output is correct
36 Correct 678 ms 60208 KB Output is correct
37 Correct 685 ms 60240 KB Output is correct
38 Correct 1158 ms 82188 KB Output is correct
39 Correct 795 ms 82180 KB Output is correct
40 Correct 1157 ms 72304 KB Output is correct
41 Correct 1746 ms 82196 KB Output is correct
42 Correct 410 ms 82232 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 58800 KB Output is correct
2 Correct 525 ms 58792 KB Output is correct
3 Correct 517 ms 58804 KB Output is correct
4 Correct 472 ms 58820 KB Output is correct
5 Correct 465 ms 58740 KB Output is correct
6 Correct 474 ms 58828 KB Output is correct
7 Correct 492 ms 58800 KB Output is correct
8 Correct 518 ms 58720 KB Output is correct
9 Correct 483 ms 58800 KB Output is correct
10 Correct 491 ms 58820 KB Output is correct
11 Correct 483 ms 58820 KB Output is correct
12 Correct 480 ms 58720 KB Output is correct
13 Correct 487 ms 58796 KB Output is correct
14 Correct 481 ms 58820 KB Output is correct
15 Correct 503 ms 58936 KB Output is correct
16 Correct 499 ms 58820 KB Output is correct
17 Correct 491 ms 58800 KB Output is correct
18 Correct 499 ms 58892 KB Output is correct
19 Correct 525 ms 58820 KB Output is correct
20 Correct 554 ms 58820 KB Output is correct
21 Correct 499 ms 58744 KB Output is correct
22 Correct 437 ms 58832 KB Output is correct
23 Correct 492 ms 58696 KB Output is correct
24 Correct 472 ms 58820 KB Output is correct
25 Correct 505 ms 58828 KB Output is correct
26 Correct 480 ms 58736 KB Output is correct
27 Correct 490 ms 58820 KB Output is correct
28 Correct 450 ms 58928 KB Output is correct
29 Correct 501 ms 58800 KB Output is correct
30 Correct 441 ms 58764 KB Output is correct
31 Incorrect 499 ms 58812 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 58800 KB Output is correct
2 Correct 525 ms 58792 KB Output is correct
3 Correct 517 ms 58804 KB Output is correct
4 Correct 472 ms 58820 KB Output is correct
5 Correct 465 ms 58740 KB Output is correct
6 Correct 474 ms 58828 KB Output is correct
7 Correct 492 ms 58800 KB Output is correct
8 Correct 518 ms 58720 KB Output is correct
9 Correct 483 ms 58800 KB Output is correct
10 Correct 491 ms 58820 KB Output is correct
11 Correct 483 ms 58820 KB Output is correct
12 Correct 480 ms 58720 KB Output is correct
13 Correct 487 ms 58796 KB Output is correct
14 Correct 481 ms 58820 KB Output is correct
15 Correct 503 ms 58936 KB Output is correct
16 Correct 499 ms 58820 KB Output is correct
17 Correct 491 ms 58800 KB Output is correct
18 Correct 499 ms 58892 KB Output is correct
19 Correct 1651 ms 82288 KB Output is correct
20 Correct 1329 ms 82276 KB Output is correct
21 Correct 1243 ms 81468 KB Output is correct
22 Correct 1146 ms 80420 KB Output is correct
23 Correct 742 ms 60232 KB Output is correct
24 Correct 778 ms 60176 KB Output is correct
25 Correct 1322 ms 82272 KB Output is correct
26 Correct 1295 ms 82196 KB Output is correct
27 Correct 1406 ms 82208 KB Output is correct
28 Correct 1386 ms 82280 KB Output is correct
29 Correct 1362 ms 82116 KB Output is correct
30 Correct 757 ms 60236 KB Output is correct
31 Correct 1382 ms 82216 KB Output is correct
32 Correct 1315 ms 81392 KB Output is correct
33 Correct 719 ms 60164 KB Output is correct
34 Correct 1379 ms 82284 KB Output is correct
35 Correct 1096 ms 79376 KB Output is correct
36 Correct 678 ms 60208 KB Output is correct
37 Correct 685 ms 60240 KB Output is correct
38 Correct 1158 ms 82188 KB Output is correct
39 Correct 795 ms 82180 KB Output is correct
40 Correct 1157 ms 72304 KB Output is correct
41 Correct 1746 ms 82196 KB Output is correct
42 Correct 410 ms 82232 KB Output is correct
43 Correct 525 ms 58820 KB Output is correct
44 Correct 554 ms 58820 KB Output is correct
45 Correct 499 ms 58744 KB Output is correct
46 Correct 437 ms 58832 KB Output is correct
47 Correct 492 ms 58696 KB Output is correct
48 Correct 472 ms 58820 KB Output is correct
49 Correct 505 ms 58828 KB Output is correct
50 Correct 480 ms 58736 KB Output is correct
51 Correct 490 ms 58820 KB Output is correct
52 Correct 450 ms 58928 KB Output is correct
53 Correct 501 ms 58800 KB Output is correct
54 Correct 441 ms 58764 KB Output is correct
55 Incorrect 499 ms 58812 KB Output isn't correct
56 Halted 0 ms 0 KB -