oj.uz

Submission #430465

# Submission time Handle Problem Language Result Execution time Memory
430465 2021-06-16T14:10:09 Z 2fat2code Crossing (JOI21_crossing) C++17
100 / 100
 932 ms 17100 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int nmax = 200005;
const int mod = 1e9 + 7;
const int p = 101;

int n, q, pw[nmax], tree[4*nmax], lazy[4*nmax], sump[nmax];
string Sa, Sb, Sc, T0;

int generatehash(string aux){
    int hsh = 0;
    for(int i=0;i<(int)aux.size();i++){
        hsh = (hsh + pw[i] * (aux[i] - '0') % mod) % mod;
    }
    return hsh;
}

vector<int>vecc;

string comb(string a, string b){
    string aux = "";
    for(int t=0;t<n;t++){
        if(a[t] == b[t]){
            aux += a[t];
        }
        else if(a[t] != '1' && b[t] != '1'){
            aux += '1';
        }
        else if(a[t] != '0' && b[t] != '0'){
            aux += '0';
        }
        else{
            aux += '2';
        }
    }
    return aux;
}

void calc(){
    string aux = comb(Sa, Sb);
    vecc.push_back(generatehash(aux));
    aux = comb(Sa, Sc);
    vecc.push_back(generatehash(aux));
    aux = comb(Sb, Sc);
    vecc.push_back(generatehash(aux));
    aux = comb(Sa, Sb);
    aux = comb(aux, Sc);
    vecc.push_back(generatehash(aux));
    aux = comb(Sb, Sc);
    aux = comb(aux, Sa);
    vecc.push_back(generatehash(aux));
    aux = comb(Sa, Sc);
    aux = comb(aux, Sb);
    vecc.push_back(generatehash(aux));
}

void build(int l, int r, int nod){
    if(l == r){
        tree[nod] = (T0[l - 1] - '0');
    }
    else{
        int mid = l + (r - l) / 2;
        build(l, mid, 2*nod);
        build(mid+1, r, 2*nod+1);
        tree[nod] = (tree[2*nod] + pw[(mid - l + 1)] * tree[2*nod + 1] % mod) % mod;
    }
}

void push(int l, int r, int nod){
    if(lazy[nod] >= 1){
        tree[nod] = (lazy[nod] - 1LL) * sump[r - l] % mod;
        if(l != r){
            lazy[2*nod] = lazy[nod];
            lazy[2*nod+1] = lazy[nod];
        }
        lazy[nod] = 0;
    }
}

void update(int l, int r, int le, int ri, int val, int nod){
    push(l, r, nod);
    if(l > ri || r < le){
        return;
    }
    else if(l >= le && r <= ri){
        lazy[nod] = val;
        push(l, r, nod);
    }
    else{
        int mid = l + (r - l) / 2;
        update(l, mid, le, ri, val, 2*nod);
        update(mid + 1, r, le, ri, val, 2*nod + 1);
        tree[nod] = (tree[2*nod] + pw[(mid - l + 1)] * tree[2*nod + 1] % mod) % mod;
    }
}

bool check(){
    push(1, n, 1);
    for(auto it : vecc){
        if(it == tree[1]){
            return true;
        }
    }
    return false;
}


int32_t main(){
    //ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    //freopen("input.in", "r", stdin);
    pw[0] = 1;
    sump[0] = 1;
    for(int i=1;i<nmax;i++){
        pw[i] = pw[i-1] * p % mod;
        sump[i] = (sump[i-1] + pw[i]) % mod;
    }
    cin >> n >> Sa >> Sb >> Sc >> q >> T0;
    for(auto &it : Sa){
        if(it == 'J') it = '0';
        else if(it == 'O') it = '1';
        else it = '2';
    }
    for(auto &it : Sb){
        if(it == 'J') it = '0';
        else if(it == 'O') it = '1';
        else it = '2';
    }
    for(auto &it : Sc){
        if(it == 'J') it = '0';
        else if(it == 'O') it = '1';
        else it = '2';
    }
    for(auto &it : T0){
        if(it == 'J') it = '0';
        else if(it == 'O') it = '1';
        else it = '2';
    }
    vecc.push_back(generatehash(Sa));
    vecc.push_back(generatehash(Sb));
    vecc.push_back(generatehash(Sc));
    calc();
    build(1, n, 1);
    cout << (check() == true ? "Yes" : "No") << '\n';
    for(int i=1;i<=q;i++){
        int l, r;
        char c;
        cin >> l >> r >> c;
        int val;
        if(c == 'J') val = 1;
        else if(c == 'O') val = 2;
        else val = 3;
        update(1, n, l, r, val, 1);
        cout << (check() == true ? "Yes" : "No") << '\n';
    }
}

// 1. Solve the problem
// 2. ???
// 3. Profit

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 4044 KB Output is correct
2 Correct 492 ms 3908 KB Output is correct
3 Correct 497 ms 4036 KB Output is correct
4 Correct 507 ms 3964 KB Output is correct
5 Correct 447 ms 3908 KB Output is correct
6 Correct 521 ms 3948 KB Output is correct
7 Correct 482 ms 4104 KB Output is correct
8 Correct 548 ms 3944 KB Output is correct
9 Correct 467 ms 3992 KB Output is correct
10 Correct 514 ms 4004 KB Output is correct
11 Correct 480 ms 4092 KB Output is correct
12 Correct 490 ms 4016 KB Output is correct
13 Correct 472 ms 4092 KB Output is correct
14 Correct 473 ms 4040 KB Output is correct
15 Correct 526 ms 4032 KB Output is correct
16 Correct 467 ms 3936 KB Output is correct
17 Correct 517 ms 4036 KB Output is correct
18 Correct 466 ms 4036 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 4044 KB Output is correct
2 Correct 492 ms 3908 KB Output is correct
3 Correct 497 ms 4036 KB Output is correct
4 Correct 507 ms 3964 KB Output is correct
5 Correct 447 ms 3908 KB Output is correct
6 Correct 521 ms 3948 KB Output is correct
7 Correct 482 ms 4104 KB Output is correct
8 Correct 548 ms 3944 KB Output is correct
9 Correct 467 ms 3992 KB Output is correct
10 Correct 514 ms 4004 KB Output is correct
11 Correct 480 ms 4092 KB Output is correct
12 Correct 490 ms 4016 KB Output is correct
13 Correct 472 ms 4092 KB Output is correct
14 Correct 473 ms 4040 KB Output is correct
15 Correct 526 ms 4032 KB Output is correct
16 Correct 467 ms 3936 KB Output is correct
17 Correct 517 ms 4036 KB Output is correct
18 Correct 466 ms 4036 KB Output is correct
19 Correct 912 ms 13532 KB Output is correct
20 Correct 919 ms 10308 KB Output is correct
21 Correct 739 ms 13472 KB Output is correct
22 Correct 742 ms 13296 KB Output is correct
23 Correct 677 ms 4544 KB Output is correct
24 Correct 611 ms 4692 KB Output is correct
25 Correct 749 ms 13532 KB Output is correct
26 Correct 812 ms 13528 KB Output is correct
27 Correct 829 ms 13660 KB Output is correct
28 Correct 833 ms 13604 KB Output is correct
29 Correct 828 ms 13456 KB Output is correct
30 Correct 583 ms 4564 KB Output is correct
31 Correct 786 ms 13456 KB Output is correct
32 Correct 739 ms 13372 KB Output is correct
33 Correct 566 ms 4756 KB Output is correct
34 Correct 812 ms 13544 KB Output is correct
35 Correct 672 ms 13260 KB Output is correct
36 Correct 544 ms 4596 KB Output is correct
37 Correct 560 ms 4548 KB Output is correct
38 Correct 729 ms 10296 KB Output is correct
39 Correct 648 ms 9496 KB Output is correct
40 Correct 642 ms 8956 KB Output is correct
41 Correct 873 ms 13832 KB Output is correct
42 Correct 520 ms 9652 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 4044 KB Output is correct
2 Correct 492 ms 3908 KB Output is correct
3 Correct 497 ms 4036 KB Output is correct
4 Correct 507 ms 3964 KB Output is correct
5 Correct 447 ms 3908 KB Output is correct
6 Correct 521 ms 3948 KB Output is correct
7 Correct 482 ms 4104 KB Output is correct
8 Correct 548 ms 3944 KB Output is correct
9 Correct 467 ms 3992 KB Output is correct
10 Correct 514 ms 4004 KB Output is correct
11 Correct 480 ms 4092 KB Output is correct
12 Correct 490 ms 4016 KB Output is correct
13 Correct 472 ms 4092 KB Output is correct
14 Correct 473 ms 4040 KB Output is correct
15 Correct 526 ms 4032 KB Output is correct
16 Correct 467 ms 3936 KB Output is correct
17 Correct 517 ms 4036 KB Output is correct
18 Correct 466 ms 4036 KB Output is correct
19 Correct 513 ms 3972 KB Output is correct
20 Correct 503 ms 3960 KB Output is correct
21 Correct 483 ms 4044 KB Output is correct
22 Correct 429 ms 3908 KB Output is correct
23 Correct 460 ms 3956 KB Output is correct
24 Correct 463 ms 3992 KB Output is correct
25 Correct 533 ms 4052 KB Output is correct
26 Correct 465 ms 3944 KB Output is correct
27 Correct 478 ms 3968 KB Output is correct
28 Correct 432 ms 4100 KB Output is correct
29 Correct 473 ms 4072 KB Output is correct
30 Correct 436 ms 3980 KB Output is correct
31 Correct 523 ms 4084 KB Output is correct
32 Correct 478 ms 3924 KB Output is correct
33 Correct 487 ms 4004 KB Output is correct
34 Correct 436 ms 3892 KB Output is correct
35 Correct 521 ms 3988 KB Output is correct
36 Correct 472 ms 3940 KB Output is correct
37 Correct 513 ms 4024 KB Output is correct
38 Correct 521 ms 3928 KB Output is correct
39 Correct 474 ms 4072 KB Output is correct
40 Correct 472 ms 4132 KB Output is correct
41 Correct 477 ms 3928 KB Output is correct
42 Correct 536 ms 3984 KB Output is correct
43 Correct 469 ms 3980 KB Output is correct
44 Correct 476 ms 3976 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 4044 KB Output is correct
2 Correct 492 ms 3908 KB Output is correct
3 Correct 497 ms 4036 KB Output is correct
4 Correct 507 ms 3964 KB Output is correct
5 Correct 447 ms 3908 KB Output is correct
6 Correct 521 ms 3948 KB Output is correct
7 Correct 482 ms 4104 KB Output is correct
8 Correct 548 ms 3944 KB Output is correct
9 Correct 467 ms 3992 KB Output is correct
10 Correct 514 ms 4004 KB Output is correct
11 Correct 480 ms 4092 KB Output is correct
12 Correct 490 ms 4016 KB Output is correct
13 Correct 472 ms 4092 KB Output is correct
14 Correct 473 ms 4040 KB Output is correct
15 Correct 526 ms 4032 KB Output is correct
16 Correct 467 ms 3936 KB Output is correct
17 Correct 517 ms 4036 KB Output is correct
18 Correct 466 ms 4036 KB Output is correct
19 Correct 912 ms 13532 KB Output is correct
20 Correct 919 ms 10308 KB Output is correct
21 Correct 739 ms 13472 KB Output is correct
22 Correct 742 ms 13296 KB Output is correct
23 Correct 677 ms 4544 KB Output is correct
24 Correct 611 ms 4692 KB Output is correct
25 Correct 749 ms 13532 KB Output is correct
26 Correct 812 ms 13528 KB Output is correct
27 Correct 829 ms 13660 KB Output is correct
28 Correct 833 ms 13604 KB Output is correct
29 Correct 828 ms 13456 KB Output is correct
30 Correct 583 ms 4564 KB Output is correct
31 Correct 786 ms 13456 KB Output is correct
32 Correct 739 ms 13372 KB Output is correct
33 Correct 566 ms 4756 KB Output is correct
34 Correct 812 ms 13544 KB Output is correct
35 Correct 672 ms 13260 KB Output is correct
36 Correct 544 ms 4596 KB Output is correct
37 Correct 560 ms 4548 KB Output is correct
38 Correct 729 ms 10296 KB Output is correct
39 Correct 648 ms 9496 KB Output is correct
40 Correct 642 ms 8956 KB Output is correct
41 Correct 873 ms 13832 KB Output is correct
42 Correct 520 ms 9652 KB Output is correct
43 Correct 513 ms 3972 KB Output is correct
44 Correct 503 ms 3960 KB Output is correct
45 Correct 483 ms 4044 KB Output is correct
46 Correct 429 ms 3908 KB Output is correct
47 Correct 460 ms 3956 KB Output is correct
48 Correct 463 ms 3992 KB Output is correct
49 Correct 533 ms 4052 KB Output is correct
50 Correct 465 ms 3944 KB Output is correct
51 Correct 478 ms 3968 KB Output is correct
52 Correct 432 ms 4100 KB Output is correct
53 Correct 473 ms 4072 KB Output is correct
54 Correct 436 ms 3980 KB Output is correct
55 Correct 523 ms 4084 KB Output is correct
56 Correct 478 ms 3924 KB Output is correct
57 Correct 487 ms 4004 KB Output is correct
58 Correct 436 ms 3892 KB Output is correct
59 Correct 521 ms 3988 KB Output is correct
60 Correct 472 ms 3940 KB Output is correct
61 Correct 513 ms 4024 KB Output is correct
62 Correct 521 ms 3928 KB Output is correct
63 Correct 474 ms 4072 KB Output is correct
64 Correct 472 ms 4132 KB Output is correct
65 Correct 477 ms 3928 KB Output is correct
66 Correct 536 ms 3984 KB Output is correct
67 Correct 469 ms 3980 KB Output is correct
68 Correct 476 ms 3976 KB Output is correct
69 Correct 754 ms 13852 KB Output is correct
70 Correct 866 ms 13224 KB Output is correct
71 Correct 596 ms 6740 KB Output is correct
72 Correct 591 ms 6912 KB Output is correct
73 Correct 579 ms 6776 KB Output is correct
74 Correct 775 ms 16580 KB Output is correct
75 Correct 608 ms 6548 KB Output is correct
76 Correct 801 ms 16936 KB Output is correct
77 Correct 768 ms 16356 KB Output is correct
78 Correct 669 ms 6788 KB Output is correct
79 Correct 636 ms 6708 KB Output is correct
80 Correct 694 ms 15548 KB Output is correct
81 Correct 623 ms 6592 KB Output is correct
82 Correct 790 ms 16464 KB Output is correct
83 Correct 761 ms 15976 KB Output is correct
84 Correct 553 ms 6752 KB Output is correct
85 Correct 568 ms 6712 KB Output is correct
86 Correct 735 ms 16216 KB Output is correct
87 Correct 794 ms 16780 KB Output is correct
88 Correct 589 ms 6588 KB Output is correct
89 Correct 808 ms 15748 KB Output is correct
90 Correct 797 ms 15184 KB Output is correct
91 Correct 628 ms 6088 KB Output is correct
92 Correct 736 ms 13908 KB Output is correct
93 Correct 648 ms 5664 KB Output is correct
94 Correct 600 ms 6168 KB Output is correct
95 Correct 673 ms 6072 KB Output is correct
96 Correct 744 ms 13216 KB Output is correct
97 Correct 652 ms 12832 KB Output is correct
98 Correct 715 ms 12192 KB Output is correct
99 Correct 932 ms 17100 KB Output is correct
100 Correct 546 ms 11984 KB Output is correct