oj.uz

Submission #430442

# Submission time Handle Problem Language Result Execution time Memory
430442 2021-06-16T13:50:28 Z 2fat2code Crossing (JOI21_crossing) C++17
26 / 100
 6342 ms 14308 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 + 9;
const int p = 41;

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

map<int,int>mp;

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<pair<string, int>>vecc;

void calc(){
    for(auto it : vecc){
        mp[it.sc] = 1;
    }
    for(int i=0;i<(int)vecc.size();i++){
        for(int j=0;j<i;j++){
            string aux;
            for(int t=0;t<n;t++){
                if(vecc[i].fr[t] == vecc[j].fr[t]){
                    aux += vecc[i].fr[t];
                }
                else if(vecc[i].fr[t] != '1' && vecc[j].fr[t] != '1'){
                    aux += '1';
                }
                else if(vecc[i].fr[t] != '0' && vecc[j].fr[t] != '0'){
                    aux += '0';
                }
                else{
                    aux += '2';
                }
            }
            int curr = generatehash(aux);
            if(mp.count(curr) == 0){
                mp[curr] = 1;
                vecc.push_back({aux, curr});
            }
        }
    }
}

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];
        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.sc == 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({Sa, generatehash(Sa)});
    vecc.push_back({Sb, generatehash(Sb)});
    vecc.push_back({Sc, 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 454 ms 3952 KB Output is correct
2 Correct 500 ms 4048 KB Output is correct
3 Correct 507 ms 4036 KB Output is correct
4 Correct 466 ms 3956 KB Output is correct
5 Correct 498 ms 4120 KB Output is correct
6 Correct 462 ms 3980 KB Output is correct
7 Correct 489 ms 4112 KB Output is correct
8 Correct 491 ms 4072 KB Output is correct
9 Correct 492 ms 3996 KB Output is correct
10 Correct 488 ms 4036 KB Output is correct
11 Correct 490 ms 4112 KB Output is correct
12 Correct 494 ms 4032 KB Output is correct
13 Correct 497 ms 4176 KB Output is correct
14 Correct 492 ms 4016 KB Output is correct
15 Correct 488 ms 4036 KB Output is correct
16 Correct 497 ms 4020 KB Output is correct
17 Correct 501 ms 4104 KB Output is correct
18 Correct 484 ms 3940 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 3952 KB Output is correct
2 Correct 500 ms 4048 KB Output is correct
3 Correct 507 ms 4036 KB Output is correct
4 Correct 466 ms 3956 KB Output is correct
5 Correct 498 ms 4120 KB Output is correct
6 Correct 462 ms 3980 KB Output is correct
7 Correct 489 ms 4112 KB Output is correct
8 Correct 491 ms 4072 KB Output is correct
9 Correct 492 ms 3996 KB Output is correct
10 Correct 488 ms 4036 KB Output is correct
11 Correct 490 ms 4112 KB Output is correct
12 Correct 494 ms 4032 KB Output is correct
13 Correct 497 ms 4176 KB Output is correct
14 Correct 492 ms 4016 KB Output is correct
15 Correct 488 ms 4036 KB Output is correct
16 Correct 497 ms 4020 KB Output is correct
17 Correct 501 ms 4104 KB Output is correct
18 Correct 484 ms 3940 KB Output is correct
19 Correct 6342 ms 14248 KB Output is correct
20 Correct 6236 ms 10956 KB Output is correct
21 Correct 5547 ms 13836 KB Output is correct
22 Correct 5061 ms 14004 KB Output is correct
23 Correct 868 ms 4672 KB Output is correct
24 Correct 878 ms 4544 KB Output is correct
25 Correct 6249 ms 14232 KB Output is correct
26 Correct 6132 ms 14308 KB Output is correct
27 Correct 6222 ms 14060 KB Output is correct
28 Correct 6235 ms 13980 KB Output is correct
29 Correct 5965 ms 14056 KB Output is correct
30 Correct 888 ms 4676 KB Output is correct
31 Correct 6256 ms 14032 KB Output is correct
32 Correct 5613 ms 14004 KB Output is correct
33 Correct 877 ms 4692 KB Output is correct
34 Correct 6201 ms 14272 KB Output is correct
35 Correct 4395 ms 13596 KB Output is correct
36 Correct 864 ms 4740 KB Output is correct
37 Correct 864 ms 4824 KB Output is correct
38 Incorrect 6066 ms 10864 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 3952 KB Output is correct
2 Correct 500 ms 4048 KB Output is correct
3 Correct 507 ms 4036 KB Output is correct
4 Correct 466 ms 3956 KB Output is correct
5 Correct 498 ms 4120 KB Output is correct
6 Correct 462 ms 3980 KB Output is correct
7 Correct 489 ms 4112 KB Output is correct
8 Correct 491 ms 4072 KB Output is correct
9 Correct 492 ms 3996 KB Output is correct
10 Correct 488 ms 4036 KB Output is correct
11 Correct 490 ms 4112 KB Output is correct
12 Correct 494 ms 4032 KB Output is correct
13 Correct 497 ms 4176 KB Output is correct
14 Correct 492 ms 4016 KB Output is correct
15 Correct 488 ms 4036 KB Output is correct
16 Correct 497 ms 4020 KB Output is correct
17 Correct 501 ms 4104 KB Output is correct
18 Correct 484 ms 3940 KB Output is correct
19 Correct 522 ms 3908 KB Output is correct
20 Correct 536 ms 4016 KB Output is correct
21 Correct 490 ms 4016 KB Output is correct
22 Correct 477 ms 4044 KB Output is correct
23 Correct 492 ms 3924 KB Output is correct
24 Correct 480 ms 3972 KB Output is correct
25 Correct 501 ms 4088 KB Output is correct
26 Correct 471 ms 4132 KB Output is correct
27 Correct 499 ms 4128 KB Output is correct
28 Correct 449 ms 3960 KB Output is correct
29 Correct 485 ms 3916 KB Output is correct
30 Correct 456 ms 3972 KB Output is correct
31 Correct 533 ms 4276 KB Output is correct
32 Correct 526 ms 4036 KB Output is correct
33 Correct 529 ms 4012 KB Output is correct
34 Correct 497 ms 3916 KB Output is correct
35 Correct 525 ms 4036 KB Output is correct
36 Correct 533 ms 3964 KB Output is correct
37 Correct 532 ms 4032 KB Output is correct
38 Correct 532 ms 4000 KB Output is correct
39 Correct 543 ms 3964 KB Output is correct
40 Correct 528 ms 4052 KB Output is correct
41 Correct 527 ms 4032 KB Output is correct
42 Correct 530 ms 4036 KB Output is correct
43 Correct 515 ms 4008 KB Output is correct
44 Correct 543 ms 4164 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 3952 KB Output is correct
2 Correct 500 ms 4048 KB Output is correct
3 Correct 507 ms 4036 KB Output is correct
4 Correct 466 ms 3956 KB Output is correct
5 Correct 498 ms 4120 KB Output is correct
6 Correct 462 ms 3980 KB Output is correct
7 Correct 489 ms 4112 KB Output is correct
8 Correct 491 ms 4072 KB Output is correct
9 Correct 492 ms 3996 KB Output is correct
10 Correct 488 ms 4036 KB Output is correct
11 Correct 490 ms 4112 KB Output is correct
12 Correct 494 ms 4032 KB Output is correct
13 Correct 497 ms 4176 KB Output is correct
14 Correct 492 ms 4016 KB Output is correct
15 Correct 488 ms 4036 KB Output is correct
16 Correct 497 ms 4020 KB Output is correct
17 Correct 501 ms 4104 KB Output is correct
18 Correct 484 ms 3940 KB Output is correct
19 Correct 6342 ms 14248 KB Output is correct
20 Correct 6236 ms 10956 KB Output is correct
21 Correct 5547 ms 13836 KB Output is correct
22 Correct 5061 ms 14004 KB Output is correct
23 Correct 868 ms 4672 KB Output is correct
24 Correct 878 ms 4544 KB Output is correct
25 Correct 6249 ms 14232 KB Output is correct
26 Correct 6132 ms 14308 KB Output is correct
27 Correct 6222 ms 14060 KB Output is correct
28 Correct 6235 ms 13980 KB Output is correct
29 Correct 5965 ms 14056 KB Output is correct
30 Correct 888 ms 4676 KB Output is correct
31 Correct 6256 ms 14032 KB Output is correct
32 Correct 5613 ms 14004 KB Output is correct
33 Correct 877 ms 4692 KB Output is correct
34 Correct 6201 ms 14272 KB Output is correct
35 Correct 4395 ms 13596 KB Output is correct
36 Correct 864 ms 4740 KB Output is correct
37 Correct 864 ms 4824 KB Output is correct
38 Incorrect 6066 ms 10864 KB Output isn't correct
39 Halted 0 ms 0 KB -