oj.uz

Submission #533852

# Submission time Handle Problem Language Result Execution time Memory
533852 2022-03-07T12:26:44 Z someone Crossing (JOI21_crossing) C++14
100 / 100
 1409 ms 56644 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
 
const int M = 1 << 18, N = 2 * M;

int n, q, ans = 0, val[3][M];

struct HashLazy {
    set<int> pos;
    int hashval[N], tag_a[N], tag_b[N], pow3[M+1], cumP[M+1], MOD;
    
    HashLazy(int mod) {
        MOD = mod;
        
        pow3[0] = 1;
        for(int i = 1; i <= M; i++)
            pow3[i] = (pow3[i-1] * 3) % MOD;
        for(int i = 1; i <= M; i++)
            cumP[i] = (pow3[i-1] + cumP[i-1]) % MOD;
        
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++) {
                int hashing = 0;
                for(int k = 0; k < n; k++)
                    hashing = (hashing * 3 + (i * (val[0][k] + val[1][k] + val[2][k]) + val[j][k]) % 3) % MOD;
                pos.insert(hashing);
            }
    }
 
    inline void updNode(int i, int a, int b, int d, int f) {
        if(a == 0) {
            tag_a[i] = 0;
            tag_b[i] = b;
            hashval[i] = (b * cumP[f - d]) % MOD;
        }
    }
     
    int update(int i, int deb, int fin, int a, int b, int d = 0, int f = M) {
        if(deb <= d && f <= fin) {
            updNode(i, a, b, d, f);
            return hashval[i];
        }
        if(f <= deb || fin <= d)
            return 0;
        
        int med = (d + f) >> 1;
        updNode(i*2, tag_a[i], tag_b[i], d, med);
        updNode(i*2+1, tag_a[i], tag_b[i], med, f);
        
        tag_a[i] = 1;
        tag_b[i] = 0;
        
        int val1 = update(i*2, deb, fin, a, b, d, med),
            val2 = update(i*2+1, deb, fin, a, b, med, f);
        
        hashval[i] = (hashval[i*2] * pow3[f-med] + hashval[i*2+1]) % MOD;
      
        if(deb < med && med < fin)
            return (val1 * pow3[fin-med] + val2) % MOD;
        else
            return max(val1, val2);
    }
    
    bool good() {
        return pos.find(update(1, 0, n, 1, 0)) != pos.end();
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < n; j++) {
            char c; cin >> c;
            if(c == 'O')
                val[i][j] = 1;
            else if(c == 'I')
                val[i][j] = 2;
        }
    }
    
    HashLazy a(1e9 + 7), b(1e9 + 9), d(1e9 + 21);
    
    cin >> q;
    for(int i = 0; i < n; i++) {
        char c; cin >> c;
        if(c == 'O') {
            a.update(1, i, i+1, 0, 1);
            b.update(1, i, i+1, 0, 1);
            d.update(1, i, i+1, 0, 1);
        } else if(c == 'I') {
            a.update(1, i, i+1, 0, 2);
            b.update(1, i, i+1, 0, 2);
            d.update(1, i, i+1, 0, 2);
        }
    }
    
    if(a.good() && b.good() && d.good())
        cout << "Yes\n";
    else
        cout << "No\n";
    
    for(int i = 0; i < q; i++) {
        char c;
        int deb, fin;
        cin >> deb >> fin >> c;
        deb--;
        if(c == 'J') {
            a.update(1, deb, fin, 0, 0);
            b.update(1, deb, fin, 0, 0);
            d.update(1, deb, fin, 0, 0);
        } else if(c == 'O') {
            a.update(1, deb, fin, 0, 1);
            b.update(1, deb, fin, 0, 1);
            d.update(1, deb, fin, 0, 1);
        } else if(c == 'I') {
            a.update(1, deb, fin, 0, 2);
            b.update(1, deb, fin, 0, 2);
            d.update(1, deb, fin, 0, 2);
        }
    
        if(a.good() && b.good() && d.good())
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 50568 KB Output is correct
2 Correct 473 ms 50892 KB Output is correct
3 Correct 508 ms 50836 KB Output is correct
4 Correct 472 ms 50912 KB Output is correct
5 Correct 508 ms 50908 KB Output is correct
6 Correct 447 ms 50884 KB Output is correct
7 Correct 529 ms 50848 KB Output is correct
8 Correct 486 ms 50852 KB Output is correct
9 Correct 478 ms 50924 KB Output is correct
10 Correct 494 ms 50884 KB Output is correct
11 Correct 457 ms 51668 KB Output is correct
12 Correct 445 ms 51680 KB Output is correct
13 Correct 459 ms 51656 KB Output is correct
14 Correct 444 ms 51676 KB Output is correct
15 Correct 469 ms 51596 KB Output is correct
16 Correct 459 ms 51628 KB Output is correct
17 Correct 452 ms 51664 KB Output is correct
18 Correct 535 ms 51576 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 50568 KB Output is correct
2 Correct 473 ms 50892 KB Output is correct
3 Correct 508 ms 50836 KB Output is correct
4 Correct 472 ms 50912 KB Output is correct
5 Correct 508 ms 50908 KB Output is correct
6 Correct 447 ms 50884 KB Output is correct
7 Correct 529 ms 50848 KB Output is correct
8 Correct 486 ms 50852 KB Output is correct
9 Correct 478 ms 50924 KB Output is correct
10 Correct 494 ms 50884 KB Output is correct
11 Correct 457 ms 51668 KB Output is correct
12 Correct 445 ms 51680 KB Output is correct
13 Correct 459 ms 51656 KB Output is correct
14 Correct 444 ms 51676 KB Output is correct
15 Correct 469 ms 51596 KB Output is correct
16 Correct 459 ms 51628 KB Output is correct
17 Correct 452 ms 51664 KB Output is correct
18 Correct 535 ms 51576 KB Output is correct
19 Correct 1409 ms 56448 KB Output is correct
20 Correct 1299 ms 56436 KB Output is correct
21 Correct 901 ms 56180 KB Output is correct
22 Correct 904 ms 55652 KB Output is correct
23 Correct 525 ms 51972 KB Output is correct
24 Correct 538 ms 51968 KB Output is correct
25 Correct 715 ms 56436 KB Output is correct
26 Correct 947 ms 56500 KB Output is correct
27 Correct 1010 ms 56476 KB Output is correct
28 Correct 811 ms 56468 KB Output is correct
29 Correct 1024 ms 56388 KB Output is correct
30 Correct 539 ms 52020 KB Output is correct
31 Correct 926 ms 56644 KB Output is correct
32 Correct 933 ms 56044 KB Output is correct
33 Correct 514 ms 52044 KB Output is correct
34 Correct 928 ms 56516 KB Output is correct
35 Correct 746 ms 55236 KB Output is correct
36 Correct 490 ms 52132 KB Output is correct
37 Correct 471 ms 52020 KB Output is correct
38 Correct 1040 ms 56508 KB Output is correct
39 Correct 659 ms 56412 KB Output is correct
40 Correct 702 ms 54876 KB Output is correct
41 Correct 1389 ms 51960 KB Output is correct
42 Correct 632 ms 52068 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 50568 KB Output is correct
2 Correct 473 ms 50892 KB Output is correct
3 Correct 508 ms 50836 KB Output is correct
4 Correct 472 ms 50912 KB Output is correct
5 Correct 508 ms 50908 KB Output is correct
6 Correct 447 ms 50884 KB Output is correct
7 Correct 529 ms 50848 KB Output is correct
8 Correct 486 ms 50852 KB Output is correct
9 Correct 478 ms 50924 KB Output is correct
10 Correct 494 ms 50884 KB Output is correct
11 Correct 457 ms 51668 KB Output is correct
12 Correct 445 ms 51680 KB Output is correct
13 Correct 459 ms 51656 KB Output is correct
14 Correct 444 ms 51676 KB Output is correct
15 Correct 469 ms 51596 KB Output is correct
16 Correct 459 ms 51628 KB Output is correct
17 Correct 452 ms 51664 KB Output is correct
18 Correct 535 ms 51576 KB Output is correct
19 Correct 414 ms 51584 KB Output is correct
20 Correct 486 ms 51640 KB Output is correct
21 Correct 408 ms 51612 KB Output is correct
22 Correct 389 ms 51580 KB Output is correct
23 Correct 416 ms 51608 KB Output is correct
24 Correct 420 ms 51528 KB Output is correct
25 Correct 429 ms 51764 KB Output is correct
26 Correct 407 ms 51496 KB Output is correct
27 Correct 431 ms 51668 KB Output is correct
28 Correct 387 ms 51480 KB Output is correct
29 Correct 429 ms 51708 KB Output is correct
30 Correct 394 ms 51512 KB Output is correct
31 Correct 415 ms 51752 KB Output is correct
32 Correct 424 ms 51116 KB Output is correct
33 Correct 412 ms 51140 KB Output is correct
34 Correct 393 ms 51148 KB Output is correct
35 Correct 418 ms 51140 KB Output is correct
36 Correct 432 ms 51072 KB Output is correct
37 Correct 414 ms 51140 KB Output is correct
38 Correct 405 ms 51140 KB Output is correct
39 Correct 442 ms 51156 KB Output is correct
40 Correct 410 ms 51084 KB Output is correct
41 Correct 422 ms 51196 KB Output is correct
42 Correct 410 ms 51076 KB Output is correct
43 Correct 430 ms 51240 KB Output is correct
44 Correct 415 ms 51164 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 50568 KB Output is correct
2 Correct 473 ms 50892 KB Output is correct
3 Correct 508 ms 50836 KB Output is correct
4 Correct 472 ms 50912 KB Output is correct
5 Correct 508 ms 50908 KB Output is correct
6 Correct 447 ms 50884 KB Output is correct
7 Correct 529 ms 50848 KB Output is correct
8 Correct 486 ms 50852 KB Output is correct
9 Correct 478 ms 50924 KB Output is correct
10 Correct 494 ms 50884 KB Output is correct
11 Correct 457 ms 51668 KB Output is correct
12 Correct 445 ms 51680 KB Output is correct
13 Correct 459 ms 51656 KB Output is correct
14 Correct 444 ms 51676 KB Output is correct
15 Correct 469 ms 51596 KB Output is correct
16 Correct 459 ms 51628 KB Output is correct
17 Correct 452 ms 51664 KB Output is correct
18 Correct 535 ms 51576 KB Output is correct
19 Correct 1409 ms 56448 KB Output is correct
20 Correct 1299 ms 56436 KB Output is correct
21 Correct 901 ms 56180 KB Output is correct
22 Correct 904 ms 55652 KB Output is correct
23 Correct 525 ms 51972 KB Output is correct
24 Correct 538 ms 51968 KB Output is correct
25 Correct 715 ms 56436 KB Output is correct
26 Correct 947 ms 56500 KB Output is correct
27 Correct 1010 ms 56476 KB Output is correct
28 Correct 811 ms 56468 KB Output is correct
29 Correct 1024 ms 56388 KB Output is correct
30 Correct 539 ms 52020 KB Output is correct
31 Correct 926 ms 56644 KB Output is correct
32 Correct 933 ms 56044 KB Output is correct
33 Correct 514 ms 52044 KB Output is correct
34 Correct 928 ms 56516 KB Output is correct
35 Correct 746 ms 55236 KB Output is correct
36 Correct 490 ms 52132 KB Output is correct
37 Correct 471 ms 52020 KB Output is correct
38 Correct 1040 ms 56508 KB Output is correct
39 Correct 659 ms 56412 KB Output is correct
40 Correct 702 ms 54876 KB Output is correct
41 Correct 1389 ms 51960 KB Output is correct
42 Correct 632 ms 52068 KB Output is correct
43 Correct 414 ms 51584 KB Output is correct
44 Correct 486 ms 51640 KB Output is correct
45 Correct 408 ms 51612 KB Output is correct
46 Correct 389 ms 51580 KB Output is correct
47 Correct 416 ms 51608 KB Output is correct
48 Correct 420 ms 51528 KB Output is correct
49 Correct 429 ms 51764 KB Output is correct
50 Correct 407 ms 51496 KB Output is correct
51 Correct 431 ms 51668 KB Output is correct
52 Correct 387 ms 51480 KB Output is correct
53 Correct 429 ms 51708 KB Output is correct
54 Correct 394 ms 51512 KB Output is correct
55 Correct 415 ms 51752 KB Output is correct
56 Correct 424 ms 51116 KB Output is correct
57 Correct 412 ms 51140 KB Output is correct
58 Correct 393 ms 51148 KB Output is correct
59 Correct 418 ms 51140 KB Output is correct
60 Correct 432 ms 51072 KB Output is correct
61 Correct 414 ms 51140 KB Output is correct
62 Correct 405 ms 51140 KB Output is correct
63 Correct 442 ms 51156 KB Output is correct
64 Correct 410 ms 51084 KB Output is correct
65 Correct 422 ms 51196 KB Output is correct
66 Correct 410 ms 51076 KB Output is correct
67 Correct 430 ms 51240 KB Output is correct
68 Correct 415 ms 51164 KB Output is correct
69 Correct 1028 ms 55108 KB Output is correct
70 Correct 1212 ms 55880 KB Output is correct
71 Correct 491 ms 51652 KB Output is correct
72 Correct 467 ms 51396 KB Output is correct
73 Correct 507 ms 51396 KB Output is correct
74 Correct 894 ms 55040 KB Output is correct
75 Correct 526 ms 51196 KB Output is correct
76 Correct 849 ms 55704 KB Output is correct
77 Correct 792 ms 55072 KB Output is correct
78 Correct 469 ms 51268 KB Output is correct
79 Correct 465 ms 51268 KB Output is correct
80 Correct 765 ms 54448 KB Output is correct
81 Correct 498 ms 51468 KB Output is correct
82 Correct 838 ms 56012 KB Output is correct
83 Correct 832 ms 55732 KB Output is correct
84 Correct 475 ms 51268 KB Output is correct
85 Correct 484 ms 51524 KB Output is correct
86 Correct 993 ms 54596 KB Output is correct
87 Correct 938 ms 55848 KB Output is correct
88 Correct 506 ms 51244 KB Output is correct
89 Correct 851 ms 55176 KB Output is correct
90 Correct 905 ms 55796 KB Output is correct
91 Correct 505 ms 51316 KB Output is correct
92 Correct 734 ms 54472 KB Output is correct
93 Correct 480 ms 51256 KB Output is correct
94 Correct 483 ms 51340 KB Output is correct
95 Correct 499 ms 51268 KB Output is correct
96 Correct 841 ms 51080 KB Output is correct
97 Correct 629 ms 55748 KB Output is correct
98 Correct 700 ms 54084 KB Output is correct
99 Correct 1382 ms 54252 KB Output is correct
100 Correct 609 ms 54472 KB Output is correct