oj.uz

Submission #533816

# Submission time Handle Problem Language Result Execution time Memory
533816 2022-03-07T11:08:56 Z RaresFelix Crossing (JOI21_crossing) C++17
26 / 100
 1563 ms 191380 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 257171
int n, q;
vector<int> C[10], 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> E) : B(std::move(E)){
        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])));
    for(int i = 0; i < n; ++i) C[7].push_back(CMB(C[1][i], CMB(C[0][i], C[2][i])));
    for(int i = 0; i < n; ++i) C[8].push_back(CMB(C[2][i], CMB(C[0][i], C[2][i])));

    cin >> q;
    rd(P);
    for(int i = 0; i < 9; ++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 257 ms 145316 KB Output is correct
2 Correct 280 ms 145368 KB Output is correct
3 Correct 263 ms 145316 KB Output is correct
4 Correct 242 ms 145448 KB Output is correct
5 Correct 247 ms 145316 KB Output is correct
6 Correct 251 ms 145448 KB Output is correct
7 Correct 244 ms 145320 KB Output is correct
8 Correct 259 ms 145320 KB Output is correct
9 Correct 263 ms 145360 KB Output is correct
10 Correct 272 ms 145436 KB Output is correct
11 Correct 254 ms 145412 KB Output is correct
12 Correct 261 ms 145340 KB Output is correct
13 Correct 253 ms 145376 KB Output is correct
14 Correct 254 ms 145336 KB Output is correct
15 Correct 250 ms 145360 KB Output is correct
16 Correct 245 ms 145320 KB Output is correct
17 Correct 254 ms 145580 KB Output is correct
18 Correct 247 ms 145424 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 145316 KB Output is correct
2 Correct 280 ms 145368 KB Output is correct
3 Correct 263 ms 145316 KB Output is correct
4 Correct 242 ms 145448 KB Output is correct
5 Correct 247 ms 145316 KB Output is correct
6 Correct 251 ms 145448 KB Output is correct
7 Correct 244 ms 145320 KB Output is correct
8 Correct 259 ms 145320 KB Output is correct
9 Correct 263 ms 145360 KB Output is correct
10 Correct 272 ms 145436 KB Output is correct
11 Correct 254 ms 145412 KB Output is correct
12 Correct 261 ms 145340 KB Output is correct
13 Correct 253 ms 145376 KB Output is correct
14 Correct 254 ms 145336 KB Output is correct
15 Correct 250 ms 145360 KB Output is correct
16 Correct 245 ms 145320 KB Output is correct
17 Correct 254 ms 145580 KB Output is correct
18 Correct 247 ms 145424 KB Output is correct
19 Correct 1539 ms 191212 KB Output is correct
20 Correct 1216 ms 191200 KB Output is correct
21 Correct 1014 ms 190408 KB Output is correct
22 Correct 960 ms 188780 KB Output is correct
23 Correct 469 ms 148156 KB Output is correct
24 Correct 435 ms 148152 KB Output is correct
25 Correct 1099 ms 191220 KB Output is correct
26 Correct 1102 ms 191268 KB Output is correct
27 Correct 1259 ms 191224 KB Output is correct
28 Correct 1244 ms 191208 KB Output is correct
29 Correct 1146 ms 190840 KB Output is correct
30 Correct 498 ms 148152 KB Output is correct
31 Correct 1237 ms 191180 KB Output is correct
32 Correct 1150 ms 190004 KB Output is correct
33 Correct 462 ms 148148 KB Output is correct
34 Correct 1213 ms 191236 KB Output is correct
35 Correct 910 ms 187484 KB Output is correct
36 Correct 444 ms 148100 KB Output is correct
37 Correct 445 ms 148196 KB Output is correct
38 Correct 976 ms 191352 KB Output is correct
39 Correct 483 ms 191296 KB Output is correct
40 Correct 938 ms 170736 KB Output is correct
41 Correct 1563 ms 191320 KB Output is correct
42 Correct 183 ms 191380 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 145316 KB Output is correct
2 Correct 280 ms 145368 KB Output is correct
3 Correct 263 ms 145316 KB Output is correct
4 Correct 242 ms 145448 KB Output is correct
5 Correct 247 ms 145316 KB Output is correct
6 Correct 251 ms 145448 KB Output is correct
7 Correct 244 ms 145320 KB Output is correct
8 Correct 259 ms 145320 KB Output is correct
9 Correct 263 ms 145360 KB Output is correct
10 Correct 272 ms 145436 KB Output is correct
11 Correct 254 ms 145412 KB Output is correct
12 Correct 261 ms 145340 KB Output is correct
13 Correct 253 ms 145376 KB Output is correct
14 Correct 254 ms 145336 KB Output is correct
15 Correct 250 ms 145360 KB Output is correct
16 Correct 245 ms 145320 KB Output is correct
17 Correct 254 ms 145580 KB Output is correct
18 Correct 247 ms 145424 KB Output is correct
19 Correct 291 ms 145464 KB Output is correct
20 Correct 288 ms 145332 KB Output is correct
21 Correct 266 ms 145348 KB Output is correct
22 Correct 242 ms 145380 KB Output is correct
23 Correct 276 ms 145452 KB Output is correct
24 Correct 259 ms 145468 KB Output is correct
25 Correct 274 ms 145444 KB Output is correct
26 Correct 253 ms 145384 KB Output is correct
27 Correct 274 ms 145524 KB Output is correct
28 Correct 251 ms 145448 KB Output is correct
29 Correct 269 ms 145404 KB Output is correct
30 Correct 255 ms 145408 KB Output is correct
31 Incorrect 264 ms 145328 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 145316 KB Output is correct
2 Correct 280 ms 145368 KB Output is correct
3 Correct 263 ms 145316 KB Output is correct
4 Correct 242 ms 145448 KB Output is correct
5 Correct 247 ms 145316 KB Output is correct
6 Correct 251 ms 145448 KB Output is correct
7 Correct 244 ms 145320 KB Output is correct
8 Correct 259 ms 145320 KB Output is correct
9 Correct 263 ms 145360 KB Output is correct
10 Correct 272 ms 145436 KB Output is correct
11 Correct 254 ms 145412 KB Output is correct
12 Correct 261 ms 145340 KB Output is correct
13 Correct 253 ms 145376 KB Output is correct
14 Correct 254 ms 145336 KB Output is correct
15 Correct 250 ms 145360 KB Output is correct
16 Correct 245 ms 145320 KB Output is correct
17 Correct 254 ms 145580 KB Output is correct
18 Correct 247 ms 145424 KB Output is correct
19 Correct 1539 ms 191212 KB Output is correct
20 Correct 1216 ms 191200 KB Output is correct
21 Correct 1014 ms 190408 KB Output is correct
22 Correct 960 ms 188780 KB Output is correct
23 Correct 469 ms 148156 KB Output is correct
24 Correct 435 ms 148152 KB Output is correct
25 Correct 1099 ms 191220 KB Output is correct
26 Correct 1102 ms 191268 KB Output is correct
27 Correct 1259 ms 191224 KB Output is correct
28 Correct 1244 ms 191208 KB Output is correct
29 Correct 1146 ms 190840 KB Output is correct
30 Correct 498 ms 148152 KB Output is correct
31 Correct 1237 ms 191180 KB Output is correct
32 Correct 1150 ms 190004 KB Output is correct
33 Correct 462 ms 148148 KB Output is correct
34 Correct 1213 ms 191236 KB Output is correct
35 Correct 910 ms 187484 KB Output is correct
36 Correct 444 ms 148100 KB Output is correct
37 Correct 445 ms 148196 KB Output is correct
38 Correct 976 ms 191352 KB Output is correct
39 Correct 483 ms 191296 KB Output is correct
40 Correct 938 ms 170736 KB Output is correct
41 Correct 1563 ms 191320 KB Output is correct
42 Correct 183 ms 191380 KB Output is correct
43 Correct 291 ms 145464 KB Output is correct
44 Correct 288 ms 145332 KB Output is correct
45 Correct 266 ms 145348 KB Output is correct
46 Correct 242 ms 145380 KB Output is correct
47 Correct 276 ms 145452 KB Output is correct
48 Correct 259 ms 145468 KB Output is correct
49 Correct 274 ms 145444 KB Output is correct
50 Correct 253 ms 145384 KB Output is correct
51 Correct 274 ms 145524 KB Output is correct
52 Correct 251 ms 145448 KB Output is correct
53 Correct 269 ms 145404 KB Output is correct
54 Correct 255 ms 145408 KB Output is correct
55 Incorrect 264 ms 145328 KB Output isn't correct
56 Halted 0 ms 0 KB -