oj.uz

Submission #576031

# Submission time Handle Problem Language Result Execution time Memory
576031 2022-06-12T05:31:49 Z dantoh000 Crossing (JOI21_crossing) C++14
100 / 100
 817 ms 33832 KB 
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int n,q;
string s[3];
string T;
long long pow5[200005];
long long one5[200005];
map<long long, int> m;
struct node{
    int s,e,m;
    long long v;
    int la;
    node *l, *r;
    node (int _s, int _e){
        s = _s, e = _e, m = (s+e)/2;
        v = la = 0;
        if (s != e){
            l = new node(s,m);
            r = new node(m+1,e);
            v = (l->v * pow5[e-m] + r->v)%mod;
        }
        else{
            v = (T[s-1] == 'J')?1:(T[s-1]=='O')?2:3;
        }
    }
    void prop(){
        if (la){
            v = (one5[e-s]*la)%mod;
            if (s != e){
                l->la = la;
                r->la = la;
            }
            la = 0;
        }

    }
    void up(int qs, int qe, int nv){
        prop();
        if (qs == s && qe == e){
            la = nv;
            return;
        }
        if (qs > m) r->up(qs,qe,nv);
        else if (qe <= m) l->up(qs,qe,nv);
        else {l->up(qs,m,nv), r->up(m+1,qe,nv);}
        l->prop(); r->prop();
        v = (l->v * pow5[e-m] + r->v)%mod;
    }

} *root;
long long hsh(string S){
    long long ret = 0;
    for (int i = 0; i < n; i++){
        int k = (S[i] == 'J')?1:(S[i]=='O')?2:3;
        ret = (ret*5 + k)%mod;
    }
    return ret;
}
string cross(string a, string b){
    string s = "";
    for (int i = 0; i < n; i++){
        if (a[i] == b[i]) s += a[i];
        else s += ('J' + 'O' + 'I') - a[i] - b[i];
    }
    return s;
}
void dfs(string x){
    int h = hsh(x);
    if (m[h] == 1) return;
    m[h] = 1;
    ///cout << x << endl;
    for (int i = 0; i < 3; i++){
        dfs(cross(x, s[i]));
    }
}
void gen(){
    dfs(s[0]);
    dfs(s[1]);
    dfs(s[2]);
}
int main(){
    cin >> n;
    pow5[0] = one5[0] = 1;
    for (int i = 1; i <= n; i++){
        pow5[i] = (pow5[i-1]*5)%mod;
        one5[i] = one5[i-1] + pow5[i];
    }
    cin >> s[0] >> s[1] >> s[2];
    gen();
    cin >> q;
    cin >> T;

    root = new node(1,n);
    int ans = m.count(root->v);
    if (ans > 0) cout << "Yes\n";
    else cout << "No\n";
    for (int i = 0; i < q; i++){
        int l,r;
        char c;
        cin >> l >> r >> c;
        root->up(l,r,(c == 'J')?1:(c=='O')?2:3);
        root->prop();
        int ans = m.count(root->v);
        if (ans > 0) cout << "Yes\n";
        else cout << "No\n";

    }



}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 784 KB Output is correct
2 Correct 351 ms 2388 KB Output is correct
3 Correct 351 ms 2304 KB Output is correct
4 Correct 332 ms 2372 KB Output is correct
5 Correct 329 ms 2340 KB Output is correct
6 Correct 316 ms 2416 KB Output is correct
7 Correct 334 ms 2380 KB Output is correct
8 Correct 331 ms 2380 KB Output is correct
9 Correct 339 ms 2400 KB Output is correct
10 Correct 339 ms 2320 KB Output is correct
11 Correct 344 ms 2396 KB Output is correct
12 Correct 336 ms 2376 KB Output is correct
13 Correct 340 ms 2452 KB Output is correct
14 Correct 337 ms 2328 KB Output is correct
15 Correct 344 ms 2440 KB Output is correct
16 Correct 335 ms 2380 KB Output is correct
17 Correct 349 ms 2364 KB Output is correct
18 Correct 342 ms 2340 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 784 KB Output is correct
2 Correct 351 ms 2388 KB Output is correct
3 Correct 351 ms 2304 KB Output is correct
4 Correct 332 ms 2372 KB Output is correct
5 Correct 329 ms 2340 KB Output is correct
6 Correct 316 ms 2416 KB Output is correct
7 Correct 334 ms 2380 KB Output is correct
8 Correct 331 ms 2380 KB Output is correct
9 Correct 339 ms 2400 KB Output is correct
10 Correct 339 ms 2320 KB Output is correct
11 Correct 344 ms 2396 KB Output is correct
12 Correct 336 ms 2376 KB Output is correct
13 Correct 340 ms 2452 KB Output is correct
14 Correct 337 ms 2328 KB Output is correct
15 Correct 344 ms 2440 KB Output is correct
16 Correct 335 ms 2380 KB Output is correct
17 Correct 349 ms 2364 KB Output is correct
18 Correct 342 ms 2340 KB Output is correct
19 Correct 693 ms 33512 KB Output is correct
20 Correct 618 ms 33664 KB Output is correct
21 Correct 515 ms 31600 KB Output is correct
22 Correct 510 ms 28656 KB Output is correct
23 Correct 429 ms 4812 KB Output is correct
24 Correct 399 ms 4684 KB Output is correct
25 Correct 548 ms 33472 KB Output is correct
26 Correct 632 ms 33544 KB Output is correct
27 Correct 626 ms 33692 KB Output is correct
28 Correct 658 ms 33488 KB Output is correct
29 Correct 696 ms 32680 KB Output is correct
30 Correct 454 ms 4696 KB Output is correct
31 Correct 594 ms 33644 KB Output is correct
32 Correct 606 ms 30800 KB Output is correct
33 Correct 404 ms 4696 KB Output is correct
34 Correct 615 ms 33644 KB Output is correct
35 Correct 514 ms 25644 KB Output is correct
36 Correct 409 ms 4720 KB Output is correct
37 Correct 409 ms 4892 KB Output is correct
38 Correct 570 ms 33332 KB Output is correct
39 Correct 460 ms 33548 KB Output is correct
40 Correct 547 ms 23336 KB Output is correct
41 Correct 713 ms 33744 KB Output is correct
42 Correct 388 ms 33004 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 784 KB Output is correct
2 Correct 351 ms 2388 KB Output is correct
3 Correct 351 ms 2304 KB Output is correct
4 Correct 332 ms 2372 KB Output is correct
5 Correct 329 ms 2340 KB Output is correct
6 Correct 316 ms 2416 KB Output is correct
7 Correct 334 ms 2380 KB Output is correct
8 Correct 331 ms 2380 KB Output is correct
9 Correct 339 ms 2400 KB Output is correct
10 Correct 339 ms 2320 KB Output is correct
11 Correct 344 ms 2396 KB Output is correct
12 Correct 336 ms 2376 KB Output is correct
13 Correct 340 ms 2452 KB Output is correct
14 Correct 337 ms 2328 KB Output is correct
15 Correct 344 ms 2440 KB Output is correct
16 Correct 335 ms 2380 KB Output is correct
17 Correct 349 ms 2364 KB Output is correct
18 Correct 342 ms 2340 KB Output is correct
19 Correct 347 ms 2288 KB Output is correct
20 Correct 348 ms 2296 KB Output is correct
21 Correct 337 ms 2388 KB Output is correct
22 Correct 303 ms 2264 KB Output is correct
23 Correct 365 ms 2432 KB Output is correct
24 Correct 345 ms 2416 KB Output is correct
25 Correct 359 ms 2352 KB Output is correct
26 Correct 372 ms 2280 KB Output is correct
27 Correct 360 ms 2396 KB Output is correct
28 Correct 340 ms 2124 KB Output is correct
29 Correct 369 ms 2392 KB Output is correct
30 Correct 337 ms 2176 KB Output is correct
31 Correct 339 ms 2440 KB Output is correct
32 Correct 340 ms 2444 KB Output is correct
33 Correct 350 ms 2368 KB Output is correct
34 Correct 329 ms 2552 KB Output is correct
35 Correct 342 ms 2392 KB Output is correct
36 Correct 347 ms 2384 KB Output is correct
37 Correct 344 ms 2500 KB Output is correct
38 Correct 350 ms 2396 KB Output is correct
39 Correct 343 ms 2380 KB Output is correct
40 Correct 353 ms 2560 KB Output is correct
41 Correct 345 ms 2368 KB Output is correct
42 Correct 337 ms 2400 KB Output is correct
43 Correct 341 ms 2368 KB Output is correct
44 Correct 348 ms 2384 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 784 KB Output is correct
2 Correct 351 ms 2388 KB Output is correct
3 Correct 351 ms 2304 KB Output is correct
4 Correct 332 ms 2372 KB Output is correct
5 Correct 329 ms 2340 KB Output is correct
6 Correct 316 ms 2416 KB Output is correct
7 Correct 334 ms 2380 KB Output is correct
8 Correct 331 ms 2380 KB Output is correct
9 Correct 339 ms 2400 KB Output is correct
10 Correct 339 ms 2320 KB Output is correct
11 Correct 344 ms 2396 KB Output is correct
12 Correct 336 ms 2376 KB Output is correct
13 Correct 340 ms 2452 KB Output is correct
14 Correct 337 ms 2328 KB Output is correct
15 Correct 344 ms 2440 KB Output is correct
16 Correct 335 ms 2380 KB Output is correct
17 Correct 349 ms 2364 KB Output is correct
18 Correct 342 ms 2340 KB Output is correct
19 Correct 693 ms 33512 KB Output is correct
20 Correct 618 ms 33664 KB Output is correct
21 Correct 515 ms 31600 KB Output is correct
22 Correct 510 ms 28656 KB Output is correct
23 Correct 429 ms 4812 KB Output is correct
24 Correct 399 ms 4684 KB Output is correct
25 Correct 548 ms 33472 KB Output is correct
26 Correct 632 ms 33544 KB Output is correct
27 Correct 626 ms 33692 KB Output is correct
28 Correct 658 ms 33488 KB Output is correct
29 Correct 696 ms 32680 KB Output is correct
30 Correct 454 ms 4696 KB Output is correct
31 Correct 594 ms 33644 KB Output is correct
32 Correct 606 ms 30800 KB Output is correct
33 Correct 404 ms 4696 KB Output is correct
34 Correct 615 ms 33644 KB Output is correct
35 Correct 514 ms 25644 KB Output is correct
36 Correct 409 ms 4720 KB Output is correct
37 Correct 409 ms 4892 KB Output is correct
38 Correct 570 ms 33332 KB Output is correct
39 Correct 460 ms 33548 KB Output is correct
40 Correct 547 ms 23336 KB Output is correct
41 Correct 713 ms 33744 KB Output is correct
42 Correct 388 ms 33004 KB Output is correct
43 Correct 347 ms 2288 KB Output is correct
44 Correct 348 ms 2296 KB Output is correct
45 Correct 337 ms 2388 KB Output is correct
46 Correct 303 ms 2264 KB Output is correct
47 Correct 365 ms 2432 KB Output is correct
48 Correct 345 ms 2416 KB Output is correct
49 Correct 359 ms 2352 KB Output is correct
50 Correct 372 ms 2280 KB Output is correct
51 Correct 360 ms 2396 KB Output is correct
52 Correct 340 ms 2124 KB Output is correct
53 Correct 369 ms 2392 KB Output is correct
54 Correct 337 ms 2176 KB Output is correct
55 Correct 339 ms 2440 KB Output is correct
56 Correct 340 ms 2444 KB Output is correct
57 Correct 350 ms 2368 KB Output is correct
58 Correct 329 ms 2552 KB Output is correct
59 Correct 342 ms 2392 KB Output is correct
60 Correct 347 ms 2384 KB Output is correct
61 Correct 344 ms 2500 KB Output is correct
62 Correct 350 ms 2396 KB Output is correct
63 Correct 343 ms 2380 KB Output is correct
64 Correct 353 ms 2560 KB Output is correct
65 Correct 345 ms 2368 KB Output is correct
66 Correct 337 ms 2400 KB Output is correct
67 Correct 341 ms 2368 KB Output is correct
68 Correct 348 ms 2384 KB Output is correct
69 Correct 698 ms 28528 KB Output is correct
70 Correct 682 ms 33432 KB Output is correct
71 Correct 428 ms 4800 KB Output is correct
72 Correct 419 ms 4712 KB Output is correct
73 Correct 417 ms 4816 KB Output is correct
74 Correct 518 ms 28216 KB Output is correct
75 Correct 405 ms 4720 KB Output is correct
76 Correct 610 ms 33832 KB Output is correct
77 Correct 598 ms 28476 KB Output is correct
78 Correct 424 ms 4684 KB Output is correct
79 Correct 427 ms 4712 KB Output is correct
80 Correct 586 ms 24756 KB Output is correct
81 Correct 438 ms 4632 KB Output is correct
82 Correct 714 ms 33580 KB Output is correct
83 Correct 686 ms 31620 KB Output is correct
84 Correct 448 ms 4732 KB Output is correct
85 Correct 505 ms 4672 KB Output is correct
86 Correct 670 ms 26224 KB Output is correct
87 Correct 807 ms 33532 KB Output is correct
88 Correct 477 ms 4656 KB Output is correct
89 Correct 680 ms 29840 KB Output is correct
90 Correct 717 ms 33592 KB Output is correct
91 Correct 490 ms 4728 KB Output is correct
92 Correct 639 ms 25768 KB Output is correct
93 Correct 467 ms 4656 KB Output is correct
94 Correct 467 ms 4680 KB Output is correct
95 Correct 460 ms 4636 KB Output is correct
96 Correct 637 ms 33336 KB Output is correct
97 Correct 552 ms 33560 KB Output is correct
98 Correct 661 ms 23292 KB Output is correct
99 Correct 817 ms 33732 KB Output is correct
100 Correct 469 ms 33024 KB Output is correct