oj.uz

Submission #1100090

# Submission time Handle Problem Language Result Execution time Memory
1100090 2024-10-12T16:46:35 Z ShaShi Crossing (JOI21_crossing) C++17
100 / 100
 474 ms 167236 KB 
#include <bits/stdc++.h>
 
#define int long long 
 
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
 
#define F first 
#define S second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << "\n", exit(0);
#define pii pair<int, int>
#define pll pair<long long, long long>
#define endl "\n"
 
 
 
using namespace std;
typedef long long ll;
// typedef __int128_t lll;
typedef long double ld;
 
 
const int MAXN = (int)1e6 + 7;
const int MOD[] = {(int)1e9 + 11, 998244853};
const int B[] = {34, 9};
const ll INF = (ll)1e9 + 7;


 
int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, flag, q, ans, N, X, Y, inv2;
int arr[MAXN], p[2][MAXN], ps[2][3][MAXN];
string Ss[3], T; char ch;
set<pii> st;


inline void check(pii x) { 
    if (st.find(x) == st.end()) cout << "No\n";
    else cout << "Yes\n"; 
}


inline int f(char ch) {
    if (ch == 'J') return 0;
    if (ch == 'O') return 1;
    return 2;
}


inline string cross(string u, string v) {
    string res = "";

    for (int i=0; i<n; i++) {
        if (u[i] == v[i]) res.pb(u[i]);
        else if (u[i] != 'I' && v[i] != 'I') res.pb('I');
        else if (u[i] != 'O' && v[i] != 'O') res.pb('O');
        else res.pb('J');
    }

    return res;
}


inline int _get_hash(string s, int ind) {
    int res = 0;

    for (int i=0; i<n; i++) {
        if (s[i] == 'J') res = (res*B[ind] + 0)%MOD[ind];
        else if (s[i] == 'O') res = (res*B[ind] + 1)%MOD[ind];
        else res = (res*B[ind] + 2)%MOD[ind];
    }

    return res;
}

inline pii get_hash(string s) { return {_get_hash(s, 0), _get_hash(s, 1)}; }



/* Segment Tree */
#define mid ((l+r)>>1)
#define lid (id<<1)
#define rid (lid|1)



struct Node {
    pii hsh; int sz;

    Node () {}
} seg[MAXN<<2];
int lazy[MAXN<<2];


inline void set_val(int l, int r, int id, int x) {
    seg[id].hsh.F = ps[0][x][r-l];
    seg[id].hsh.S = ps[1][x][r-l];
}


inline void relax(int l, int r, int id) {
    if (lazy[id] == -1) return;

    set_val(l, mid, lid, lazy[id]); lazy[lid] = lazy[id];
    set_val(mid, r, rid, lazy[id]); lazy[rid] = lazy[id];

    lazy[id] = -1;
}


inline Node merge(Node x, Node y) {
    Node res;

    res.sz = x.sz + y.sz;
    res.hsh.F = (x.hsh.F*p[0][y.sz]%MOD[0] + y.hsh.F)%MOD[0];
    res.hsh.S = (x.hsh.S*p[1][y.sz]%MOD[1] + y.hsh.S)%MOD[1];

    return res;
}


void build(int l=0, int r=n, int id=1) {
    lazy[id] = -1;

    if (l+1 == r) {
        seg[id].sz = 1; set_val(l, r, id, f(T[l]));
        return;
    }

    build(l, mid, lid); 
    build(mid, r, rid);


    seg[id] = merge(seg[lid], seg[rid]);
}


void upd(int s, int t, int x, int l=0, int r=n, int id=1) {
    if (s >= t) return;

    if (s <= l && t >= r) {
        set_val(l, r, id, x); lazy[id] = x;

        return;
    }

    relax(l, r, id);

    if (s < mid) upd(s, t, x, l, mid, lid);
    if (t > mid) upd(s, t, x, mid, r, rid);


    seg[id] = merge(seg[lid], seg[rid]);
}

/* Segment Tree */


int32_t main() {
    #ifdef LOCAL
    freopen("inp.in", "r", stdin);
    freopen("res.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    cin >> n;

    cin >> Ss[0] >> Ss[1] >> Ss[2];

    for (int j=0; j<2; j++) {
        p[j][0] = 1;
        for (int i=1; i<MAXN; i++) p[j][i] = p[j][i-1]*B[j]%MOD[j];
    }

    for (int o=0; o<2; o++) {
        for (int j=0; j<3; j++) {
            ps[o][j][0] = 0;
            for (int i=1; i<MAXN; i++) ps[o][j][i] = (ps[o][j][i-1]*B[o] + j)%MOD[o];
        }
    }

    for (int i=0; i<3; i++) {
        st.insert(get_hash(Ss[i]));
       
        for (int j=0; j<3; j++) st.insert(get_hash(cross(Ss[i], Ss[j])));
        for (int j=0; j<3; j++) for (int k=0; k<3; k++) st.insert(get_hash(cross(cross(Ss[i], Ss[j]), Ss[k])));
    }

    cin >> q >> T; check(get_hash(T)); build();

    while (q--) {
        cin >> u >> v >> ch;

        upd(u-1, v, f(ch));

        check(seg[1].hsh);
    }

    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 159320 KB Output is correct
2 Correct 129 ms 159324 KB Output is correct
3 Correct 129 ms 159364 KB Output is correct
4 Correct 125 ms 159252 KB Output is correct
5 Correct 121 ms 159388 KB Output is correct
6 Correct 120 ms 159312 KB Output is correct
7 Correct 123 ms 159316 KB Output is correct
8 Correct 125 ms 159416 KB Output is correct
9 Correct 126 ms 159484 KB Output is correct
10 Correct 139 ms 159440 KB Output is correct
11 Correct 139 ms 159320 KB Output is correct
12 Correct 143 ms 159436 KB Output is correct
13 Correct 141 ms 159468 KB Output is correct
14 Correct 134 ms 159412 KB Output is correct
15 Correct 136 ms 159372 KB Output is correct
16 Correct 133 ms 159684 KB Output is correct
17 Correct 125 ms 159348 KB Output is correct
18 Correct 139 ms 159312 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 159320 KB Output is correct
2 Correct 129 ms 159324 KB Output is correct
3 Correct 129 ms 159364 KB Output is correct
4 Correct 125 ms 159252 KB Output is correct
5 Correct 121 ms 159388 KB Output is correct
6 Correct 120 ms 159312 KB Output is correct
7 Correct 123 ms 159316 KB Output is correct
8 Correct 125 ms 159416 KB Output is correct
9 Correct 126 ms 159484 KB Output is correct
10 Correct 139 ms 159440 KB Output is correct
11 Correct 139 ms 159320 KB Output is correct
12 Correct 143 ms 159436 KB Output is correct
13 Correct 141 ms 159468 KB Output is correct
14 Correct 134 ms 159412 KB Output is correct
15 Correct 136 ms 159372 KB Output is correct
16 Correct 133 ms 159684 KB Output is correct
17 Correct 125 ms 159348 KB Output is correct
18 Correct 139 ms 159312 KB Output is correct
19 Correct 364 ms 167064 KB Output is correct
20 Correct 393 ms 167236 KB Output is correct
21 Correct 327 ms 166776 KB Output is correct
22 Correct 308 ms 166676 KB Output is correct
23 Correct 159 ms 160660 KB Output is correct
24 Correct 158 ms 160596 KB Output is correct
25 Correct 364 ms 167092 KB Output is correct
26 Correct 334 ms 166980 KB Output is correct
27 Correct 338 ms 167056 KB Output is correct
28 Correct 319 ms 166960 KB Output is correct
29 Correct 306 ms 166976 KB Output is correct
30 Correct 165 ms 160680 KB Output is correct
31 Correct 308 ms 167092 KB Output is correct
32 Correct 297 ms 166756 KB Output is correct
33 Correct 161 ms 160596 KB Output is correct
34 Correct 327 ms 167084 KB Output is correct
35 Correct 305 ms 166176 KB Output is correct
36 Correct 175 ms 160596 KB Output is correct
37 Correct 170 ms 160580 KB Output is correct
38 Correct 336 ms 166816 KB Output is correct
39 Correct 321 ms 167060 KB Output is correct
40 Correct 272 ms 164300 KB Output is correct
41 Correct 404 ms 167224 KB Output is correct
42 Correct 245 ms 166428 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 159320 KB Output is correct
2 Correct 129 ms 159324 KB Output is correct
3 Correct 129 ms 159364 KB Output is correct
4 Correct 125 ms 159252 KB Output is correct
5 Correct 121 ms 159388 KB Output is correct
6 Correct 120 ms 159312 KB Output is correct
7 Correct 123 ms 159316 KB Output is correct
8 Correct 125 ms 159416 KB Output is correct
9 Correct 126 ms 159484 KB Output is correct
10 Correct 139 ms 159440 KB Output is correct
11 Correct 139 ms 159320 KB Output is correct
12 Correct 143 ms 159436 KB Output is correct
13 Correct 141 ms 159468 KB Output is correct
14 Correct 134 ms 159412 KB Output is correct
15 Correct 136 ms 159372 KB Output is correct
16 Correct 133 ms 159684 KB Output is correct
17 Correct 125 ms 159348 KB Output is correct
18 Correct 139 ms 159312 KB Output is correct
19 Correct 137 ms 159272 KB Output is correct
20 Correct 145 ms 159316 KB Output is correct
21 Correct 132 ms 159312 KB Output is correct
22 Correct 127 ms 159312 KB Output is correct
23 Correct 142 ms 159336 KB Output is correct
24 Correct 133 ms 159312 KB Output is correct
25 Correct 136 ms 159312 KB Output is correct
26 Correct 132 ms 159316 KB Output is correct
27 Correct 129 ms 159312 KB Output is correct
28 Correct 119 ms 159064 KB Output is correct
29 Correct 122 ms 159312 KB Output is correct
30 Correct 122 ms 159312 KB Output is correct
31 Correct 126 ms 159316 KB Output is correct
32 Correct 127 ms 159320 KB Output is correct
33 Correct 132 ms 159296 KB Output is correct
34 Correct 121 ms 159312 KB Output is correct
35 Correct 132 ms 159316 KB Output is correct
36 Correct 145 ms 159436 KB Output is correct
37 Correct 136 ms 159316 KB Output is correct
38 Correct 142 ms 159252 KB Output is correct
39 Correct 149 ms 159316 KB Output is correct
40 Correct 136 ms 159316 KB Output is correct
41 Correct 135 ms 159312 KB Output is correct
42 Correct 136 ms 159312 KB Output is correct
43 Correct 136 ms 159336 KB Output is correct
44 Correct 129 ms 159372 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 159320 KB Output is correct
2 Correct 129 ms 159324 KB Output is correct
3 Correct 129 ms 159364 KB Output is correct
4 Correct 125 ms 159252 KB Output is correct
5 Correct 121 ms 159388 KB Output is correct
6 Correct 120 ms 159312 KB Output is correct
7 Correct 123 ms 159316 KB Output is correct
8 Correct 125 ms 159416 KB Output is correct
9 Correct 126 ms 159484 KB Output is correct
10 Correct 139 ms 159440 KB Output is correct
11 Correct 139 ms 159320 KB Output is correct
12 Correct 143 ms 159436 KB Output is correct
13 Correct 141 ms 159468 KB Output is correct
14 Correct 134 ms 159412 KB Output is correct
15 Correct 136 ms 159372 KB Output is correct
16 Correct 133 ms 159684 KB Output is correct
17 Correct 125 ms 159348 KB Output is correct
18 Correct 139 ms 159312 KB Output is correct
19 Correct 364 ms 167064 KB Output is correct
20 Correct 393 ms 167236 KB Output is correct
21 Correct 327 ms 166776 KB Output is correct
22 Correct 308 ms 166676 KB Output is correct
23 Correct 159 ms 160660 KB Output is correct
24 Correct 158 ms 160596 KB Output is correct
25 Correct 364 ms 167092 KB Output is correct
26 Correct 334 ms 166980 KB Output is correct
27 Correct 338 ms 167056 KB Output is correct
28 Correct 319 ms 166960 KB Output is correct
29 Correct 306 ms 166976 KB Output is correct
30 Correct 165 ms 160680 KB Output is correct
31 Correct 308 ms 167092 KB Output is correct
32 Correct 297 ms 166756 KB Output is correct
33 Correct 161 ms 160596 KB Output is correct
34 Correct 327 ms 167084 KB Output is correct
35 Correct 305 ms 166176 KB Output is correct
36 Correct 175 ms 160596 KB Output is correct
37 Correct 170 ms 160580 KB Output is correct
38 Correct 336 ms 166816 KB Output is correct
39 Correct 321 ms 167060 KB Output is correct
40 Correct 272 ms 164300 KB Output is correct
41 Correct 404 ms 167224 KB Output is correct
42 Correct 245 ms 166428 KB Output is correct
43 Correct 137 ms 159272 KB Output is correct
44 Correct 145 ms 159316 KB Output is correct
45 Correct 132 ms 159312 KB Output is correct
46 Correct 127 ms 159312 KB Output is correct
47 Correct 142 ms 159336 KB Output is correct
48 Correct 133 ms 159312 KB Output is correct
49 Correct 136 ms 159312 KB Output is correct
50 Correct 132 ms 159316 KB Output is correct
51 Correct 129 ms 159312 KB Output is correct
52 Correct 119 ms 159064 KB Output is correct
53 Correct 122 ms 159312 KB Output is correct
54 Correct 122 ms 159312 KB Output is correct
55 Correct 126 ms 159316 KB Output is correct
56 Correct 127 ms 159320 KB Output is correct
57 Correct 132 ms 159296 KB Output is correct
58 Correct 121 ms 159312 KB Output is correct
59 Correct 132 ms 159316 KB Output is correct
60 Correct 145 ms 159436 KB Output is correct
61 Correct 136 ms 159316 KB Output is correct
62 Correct 142 ms 159252 KB Output is correct
63 Correct 149 ms 159316 KB Output is correct
64 Correct 136 ms 159316 KB Output is correct
65 Correct 135 ms 159312 KB Output is correct
66 Correct 136 ms 159312 KB Output is correct
67 Correct 136 ms 159336 KB Output is correct
68 Correct 129 ms 159372 KB Output is correct
69 Correct 420 ms 166248 KB Output is correct
70 Correct 474 ms 166864 KB Output is correct
71 Correct 174 ms 160708 KB Output is correct
72 Correct 167 ms 160596 KB Output is correct
73 Correct 173 ms 160596 KB Output is correct
74 Correct 373 ms 166376 KB Output is correct
75 Correct 171 ms 160660 KB Output is correct
76 Correct 416 ms 167060 KB Output is correct
77 Correct 377 ms 166512 KB Output is correct
78 Correct 181 ms 160712 KB Output is correct
79 Correct 191 ms 160548 KB Output is correct
80 Correct 383 ms 166196 KB Output is correct
81 Correct 182 ms 160596 KB Output is correct
82 Correct 430 ms 167052 KB Output is correct
83 Correct 411 ms 166924 KB Output is correct
84 Correct 168 ms 160596 KB Output is correct
85 Correct 169 ms 160596 KB Output is correct
86 Correct 280 ms 166332 KB Output is correct
87 Correct 325 ms 166944 KB Output is correct
88 Correct 172 ms 160596 KB Output is correct
89 Correct 321 ms 166704 KB Output is correct
90 Correct 317 ms 167048 KB Output is correct
91 Correct 177 ms 160592 KB Output is correct
92 Correct 366 ms 166468 KB Output is correct
93 Correct 188 ms 160548 KB Output is correct
94 Correct 189 ms 160600 KB Output is correct
95 Correct 179 ms 160596 KB Output is correct
96 Correct 359 ms 166812 KB Output is correct
97 Correct 328 ms 167080 KB Output is correct
98 Correct 334 ms 164228 KB Output is correct
99 Correct 458 ms 167152 KB Output is correct
100 Correct 328 ms 166376 KB Output is correct