oj.uz

Submission #430443

# Submission time Handle Problem Language Result Execution time Memory
430443 2021-06-16T13:53:10 Z 2fat2code Crossing (JOI21_crossing) C++17
26 / 100
 6881 ms 14416 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 = 101;

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 459 ms 4092 KB Output is correct
2 Correct 501 ms 4056 KB Output is correct
3 Correct 497 ms 3988 KB Output is correct
4 Correct 472 ms 4008 KB Output is correct
5 Correct 471 ms 4008 KB Output is correct
6 Correct 459 ms 4072 KB Output is correct
7 Correct 488 ms 4036 KB Output is correct
8 Correct 483 ms 4036 KB Output is correct
9 Correct 511 ms 4008 KB Output is correct
10 Correct 502 ms 4212 KB Output is correct
11 Correct 507 ms 3988 KB Output is correct
12 Correct 499 ms 4064 KB Output is correct
13 Correct 487 ms 3908 KB Output is correct
14 Correct 492 ms 4028 KB Output is correct
15 Correct 485 ms 4164 KB Output is correct
16 Correct 485 ms 4036 KB Output is correct
17 Correct 493 ms 3992 KB Output is correct
18 Correct 489 ms 4044 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 4092 KB Output is correct
2 Correct 501 ms 4056 KB Output is correct
3 Correct 497 ms 3988 KB Output is correct
4 Correct 472 ms 4008 KB Output is correct
5 Correct 471 ms 4008 KB Output is correct
6 Correct 459 ms 4072 KB Output is correct
7 Correct 488 ms 4036 KB Output is correct
8 Correct 483 ms 4036 KB Output is correct
9 Correct 511 ms 4008 KB Output is correct
10 Correct 502 ms 4212 KB Output is correct
11 Correct 507 ms 3988 KB Output is correct
12 Correct 499 ms 4064 KB Output is correct
13 Correct 487 ms 3908 KB Output is correct
14 Correct 492 ms 4028 KB Output is correct
15 Correct 485 ms 4164 KB Output is correct
16 Correct 485 ms 4036 KB Output is correct
17 Correct 493 ms 3992 KB Output is correct
18 Correct 489 ms 4044 KB Output is correct
19 Correct 6291 ms 14416 KB Output is correct
20 Correct 6184 ms 10868 KB Output is correct
21 Correct 5601 ms 14104 KB Output is correct
22 Correct 4993 ms 13756 KB Output is correct
23 Correct 874 ms 4712 KB Output is correct
24 Correct 892 ms 4720 KB Output is correct
25 Correct 6379 ms 14004 KB Output is correct
26 Correct 6419 ms 13944 KB Output is correct
27 Correct 6523 ms 13968 KB Output is correct
28 Correct 6881 ms 13908 KB Output is correct
29 Correct 6089 ms 13960 KB Output is correct
30 Correct 866 ms 4548 KB Output is correct
31 Correct 6286 ms 13892 KB Output is correct
32 Correct 5790 ms 14096 KB Output is correct
33 Correct 888 ms 4816 KB Output is correct
34 Correct 6301 ms 13896 KB Output is correct
35 Correct 4515 ms 13516 KB Output is correct
36 Correct 871 ms 4640 KB Output is correct
37 Correct 882 ms 4644 KB Output is correct
38 Incorrect 6172 ms 11084 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 459 ms 4092 KB Output is correct
2 Correct 501 ms 4056 KB Output is correct
3 Correct 497 ms 3988 KB Output is correct
4 Correct 472 ms 4008 KB Output is correct
5 Correct 471 ms 4008 KB Output is correct
6 Correct 459 ms 4072 KB Output is correct
7 Correct 488 ms 4036 KB Output is correct
8 Correct 483 ms 4036 KB Output is correct
9 Correct 511 ms 4008 KB Output is correct
10 Correct 502 ms 4212 KB Output is correct
11 Correct 507 ms 3988 KB Output is correct
12 Correct 499 ms 4064 KB Output is correct
13 Correct 487 ms 3908 KB Output is correct
14 Correct 492 ms 4028 KB Output is correct
15 Correct 485 ms 4164 KB Output is correct
16 Correct 485 ms 4036 KB Output is correct
17 Correct 493 ms 3992 KB Output is correct
18 Correct 489 ms 4044 KB Output is correct
19 Correct 539 ms 4072 KB Output is correct
20 Correct 549 ms 3972 KB Output is correct
21 Correct 508 ms 4104 KB Output is correct
22 Correct 490 ms 3980 KB Output is correct
23 Correct 517 ms 4020 KB Output is correct
24 Correct 489 ms 4056 KB Output is correct
25 Correct 509 ms 3992 KB Output is correct
26 Correct 482 ms 4036 KB Output is correct
27 Correct 492 ms 4164 KB Output is correct
28 Correct 465 ms 3908 KB Output is correct
29 Correct 485 ms 4228 KB Output is correct
30 Correct 455 ms 4012 KB Output is correct
31 Correct 542 ms 4028 KB Output is correct
32 Correct 532 ms 4016 KB Output is correct
33 Correct 530 ms 4036 KB Output is correct
34 Correct 525 ms 3952 KB Output is correct
35 Correct 534 ms 3968 KB Output is correct
36 Correct 540 ms 3984 KB Output is correct
37 Correct 525 ms 4124 KB Output is correct
38 Correct 520 ms 4132 KB Output is correct
39 Correct 528 ms 4004 KB Output is correct
40 Correct 522 ms 3936 KB Output is correct
41 Correct 528 ms 4104 KB Output is correct
42 Correct 533 ms 4036 KB Output is correct
43 Correct 533 ms 3908 KB Output is correct
44 Correct 591 ms 4156 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 4092 KB Output is correct
2 Correct 501 ms 4056 KB Output is correct
3 Correct 497 ms 3988 KB Output is correct
4 Correct 472 ms 4008 KB Output is correct
5 Correct 471 ms 4008 KB Output is correct
6 Correct 459 ms 4072 KB Output is correct
7 Correct 488 ms 4036 KB Output is correct
8 Correct 483 ms 4036 KB Output is correct
9 Correct 511 ms 4008 KB Output is correct
10 Correct 502 ms 4212 KB Output is correct
11 Correct 507 ms 3988 KB Output is correct
12 Correct 499 ms 4064 KB Output is correct
13 Correct 487 ms 3908 KB Output is correct
14 Correct 492 ms 4028 KB Output is correct
15 Correct 485 ms 4164 KB Output is correct
16 Correct 485 ms 4036 KB Output is correct
17 Correct 493 ms 3992 KB Output is correct
18 Correct 489 ms 4044 KB Output is correct
19 Correct 6291 ms 14416 KB Output is correct
20 Correct 6184 ms 10868 KB Output is correct
21 Correct 5601 ms 14104 KB Output is correct
22 Correct 4993 ms 13756 KB Output is correct
23 Correct 874 ms 4712 KB Output is correct
24 Correct 892 ms 4720 KB Output is correct
25 Correct 6379 ms 14004 KB Output is correct
26 Correct 6419 ms 13944 KB Output is correct
27 Correct 6523 ms 13968 KB Output is correct
28 Correct 6881 ms 13908 KB Output is correct
29 Correct 6089 ms 13960 KB Output is correct
30 Correct 866 ms 4548 KB Output is correct
31 Correct 6286 ms 13892 KB Output is correct
32 Correct 5790 ms 14096 KB Output is correct
33 Correct 888 ms 4816 KB Output is correct
34 Correct 6301 ms 13896 KB Output is correct
35 Correct 4515 ms 13516 KB Output is correct
36 Correct 871 ms 4640 KB Output is correct
37 Correct 882 ms 4644 KB Output is correct
38 Incorrect 6172 ms 11084 KB Output isn't correct
39 Halted 0 ms 0 KB -