oj.uz

Submission #533810

# Submission time Handle Problem Language Result Execution time Memory
533810 2022-03-07T10:44:26 Z RaresFelix Crossing (JOI21_crossing) C++17
26 / 100
 1134 ms 87444 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
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) {
        Lz[u] = Vl[u] = Eq[u] = 0;
        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.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    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 174 ms 58820 KB Output is correct
2 Correct 205 ms 58800 KB Output is correct
3 Correct 206 ms 58820 KB Output is correct
4 Correct 165 ms 58816 KB Output is correct
5 Correct 162 ms 58784 KB Output is correct
6 Correct 164 ms 58788 KB Output is correct
7 Correct 167 ms 58816 KB Output is correct
8 Correct 174 ms 58828 KB Output is correct
9 Correct 176 ms 58816 KB Output is correct
10 Correct 178 ms 58832 KB Output is correct
11 Correct 170 ms 58812 KB Output is correct
12 Correct 168 ms 58840 KB Output is correct
13 Correct 181 ms 58792 KB Output is correct
14 Correct 171 ms 58812 KB Output is correct
15 Correct 185 ms 58748 KB Output is correct
16 Correct 175 ms 58776 KB Output is correct
17 Correct 171 ms 58712 KB Output is correct
18 Correct 167 ms 58800 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 58820 KB Output is correct
2 Correct 205 ms 58800 KB Output is correct
3 Correct 206 ms 58820 KB Output is correct
4 Correct 165 ms 58816 KB Output is correct
5 Correct 162 ms 58784 KB Output is correct
6 Correct 164 ms 58788 KB Output is correct
7 Correct 167 ms 58816 KB Output is correct
8 Correct 174 ms 58828 KB Output is correct
9 Correct 176 ms 58816 KB Output is correct
10 Correct 178 ms 58832 KB Output is correct
11 Correct 170 ms 58812 KB Output is correct
12 Correct 168 ms 58840 KB Output is correct
13 Correct 181 ms 58792 KB Output is correct
14 Correct 171 ms 58812 KB Output is correct
15 Correct 185 ms 58748 KB Output is correct
16 Correct 175 ms 58776 KB Output is correct
17 Correct 171 ms 58712 KB Output is correct
18 Correct 167 ms 58800 KB Output is correct
19 Correct 1061 ms 87444 KB Output is correct
20 Correct 815 ms 87368 KB Output is correct
21 Correct 678 ms 86852 KB Output is correct
22 Correct 674 ms 85740 KB Output is correct
23 Correct 345 ms 60488 KB Output is correct
24 Correct 320 ms 60388 KB Output is correct
25 Correct 719 ms 87404 KB Output is correct
26 Correct 741 ms 87332 KB Output is correct
27 Correct 860 ms 87368 KB Output is correct
28 Correct 896 ms 87376 KB Output is correct
29 Correct 827 ms 87104 KB Output is correct
30 Correct 383 ms 60488 KB Output is correct
31 Correct 923 ms 87320 KB Output is correct
32 Correct 845 ms 86544 KB Output is correct
33 Correct 327 ms 60484 KB Output is correct
34 Correct 889 ms 87424 KB Output is correct
35 Correct 628 ms 84760 KB Output is correct
36 Correct 336 ms 60500 KB Output is correct
37 Correct 307 ms 60508 KB Output is correct
38 Correct 693 ms 87308 KB Output is correct
39 Correct 359 ms 87420 KB Output is correct
40 Correct 629 ms 74736 KB Output is correct
41 Correct 1134 ms 87444 KB Output is correct
42 Correct 113 ms 87440 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 58820 KB Output is correct
2 Correct 205 ms 58800 KB Output is correct
3 Correct 206 ms 58820 KB Output is correct
4 Correct 165 ms 58816 KB Output is correct
5 Correct 162 ms 58784 KB Output is correct
6 Correct 164 ms 58788 KB Output is correct
7 Correct 167 ms 58816 KB Output is correct
8 Correct 174 ms 58828 KB Output is correct
9 Correct 176 ms 58816 KB Output is correct
10 Correct 178 ms 58832 KB Output is correct
11 Correct 170 ms 58812 KB Output is correct
12 Correct 168 ms 58840 KB Output is correct
13 Correct 181 ms 58792 KB Output is correct
14 Correct 171 ms 58812 KB Output is correct
15 Correct 185 ms 58748 KB Output is correct
16 Correct 175 ms 58776 KB Output is correct
17 Correct 171 ms 58712 KB Output is correct
18 Correct 167 ms 58800 KB Output is correct
19 Correct 208 ms 58656 KB Output is correct
20 Correct 204 ms 58800 KB Output is correct
21 Correct 181 ms 58692 KB Output is correct
22 Correct 164 ms 58796 KB Output is correct
23 Correct 198 ms 58748 KB Output is correct
24 Correct 177 ms 58820 KB Output is correct
25 Correct 185 ms 58760 KB Output is correct
26 Correct 179 ms 58784 KB Output is correct
27 Correct 182 ms 58716 KB Output is correct
28 Correct 169 ms 58792 KB Output is correct
29 Correct 196 ms 58848 KB Output is correct
30 Correct 170 ms 58740 KB Output is correct
31 Incorrect 181 ms 58772 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 58820 KB Output is correct
2 Correct 205 ms 58800 KB Output is correct
3 Correct 206 ms 58820 KB Output is correct
4 Correct 165 ms 58816 KB Output is correct
5 Correct 162 ms 58784 KB Output is correct
6 Correct 164 ms 58788 KB Output is correct
7 Correct 167 ms 58816 KB Output is correct
8 Correct 174 ms 58828 KB Output is correct
9 Correct 176 ms 58816 KB Output is correct
10 Correct 178 ms 58832 KB Output is correct
11 Correct 170 ms 58812 KB Output is correct
12 Correct 168 ms 58840 KB Output is correct
13 Correct 181 ms 58792 KB Output is correct
14 Correct 171 ms 58812 KB Output is correct
15 Correct 185 ms 58748 KB Output is correct
16 Correct 175 ms 58776 KB Output is correct
17 Correct 171 ms 58712 KB Output is correct
18 Correct 167 ms 58800 KB Output is correct
19 Correct 1061 ms 87444 KB Output is correct
20 Correct 815 ms 87368 KB Output is correct
21 Correct 678 ms 86852 KB Output is correct
22 Correct 674 ms 85740 KB Output is correct
23 Correct 345 ms 60488 KB Output is correct
24 Correct 320 ms 60388 KB Output is correct
25 Correct 719 ms 87404 KB Output is correct
26 Correct 741 ms 87332 KB Output is correct
27 Correct 860 ms 87368 KB Output is correct
28 Correct 896 ms 87376 KB Output is correct
29 Correct 827 ms 87104 KB Output is correct
30 Correct 383 ms 60488 KB Output is correct
31 Correct 923 ms 87320 KB Output is correct
32 Correct 845 ms 86544 KB Output is correct
33 Correct 327 ms 60484 KB Output is correct
34 Correct 889 ms 87424 KB Output is correct
35 Correct 628 ms 84760 KB Output is correct
36 Correct 336 ms 60500 KB Output is correct
37 Correct 307 ms 60508 KB Output is correct
38 Correct 693 ms 87308 KB Output is correct
39 Correct 359 ms 87420 KB Output is correct
40 Correct 629 ms 74736 KB Output is correct
41 Correct 1134 ms 87444 KB Output is correct
42 Correct 113 ms 87440 KB Output is correct
43 Correct 208 ms 58656 KB Output is correct
44 Correct 204 ms 58800 KB Output is correct
45 Correct 181 ms 58692 KB Output is correct
46 Correct 164 ms 58796 KB Output is correct
47 Correct 198 ms 58748 KB Output is correct
48 Correct 177 ms 58820 KB Output is correct
49 Correct 185 ms 58760 KB Output is correct
50 Correct 179 ms 58784 KB Output is correct
51 Correct 182 ms 58716 KB Output is correct
52 Correct 169 ms 58792 KB Output is correct
53 Correct 196 ms 58848 KB Output is correct
54 Correct 170 ms 58740 KB Output is correct
55 Incorrect 181 ms 58772 KB Output isn't correct
56 Halted 0 ms 0 KB -