oj.uz

Submission #423205

# Submission time Handle Problem Language Result Execution time Memory
423205 2021-06-10T20:00:30 Z MKopchev Crossing (JOI21_crossing) C++14
49 / 100
 747 ms 19256 KB 
#include<bits/stdc++.h>
using namespace std;

const int base=23,mod=1e9+7,nmax=2e5+42;

int n;
string inp[3];

long long pwr[nmax],mem_pref[nmax];

string t;

set<string> valid;

int order[3]={0,1,2};

int hsh(char c)
{
    if(c=='J')return 1;
    if(c=='O')return 2;
    return 3;
}

struct info
{
    int lazy;
    long long sum;
    int SZ;
};
info tree[4*nmax];

info actual(info cur)
{
    if(cur.lazy)
    {
        cur.sum=cur.lazy*mem_pref[cur.SZ-1]%mod;
        cur.lazy=0;
    }
    return cur;
}
info my_merge(info a,info b)
{
    a=actual(a);
    b=actual(b);

    a.sum=(a.sum*pwr[b.SZ]+b.sum)%mod;
    a.SZ=(a.SZ+b.SZ);

    return a;
}

void build(int node,int l,int r)
{
    if(l==r)
    {
        tree[node].sum=hsh(t[l]);
        tree[node].SZ=1;
        return;
    }

    int av=(l+r)/2;

    build(node*2,l,av);
    build(node*2+1,av+1,r);

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}

void push(int node)
{
    if(tree[node].lazy)
    {
        tree[node*2].lazy=tree[node].lazy;
        tree[node*2+1].lazy=tree[node].lazy;

        tree[node].lazy=0;
    }
}
void update(int node,int l,int r,int lq,int rq,int val)
{
    if(l==lq&&r==rq)
    {
        tree[node].lazy=val;
        return;
    }

    push(node);

    int av=(l+r)/2;

    if(lq<=av)update(node*2,l,av,lq,min(av,rq),val);
    if(av<rq)update(node*2+1,av+1,r,max(av+1,lq),rq,val);

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}
set<long long> valid_hsh;

void check()
{
    if(valid_hsh.count(actual(tree[1]).sum))cout<<"Yes\n";
    else cout<<"No\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();

    pwr[0]=1;
    for(int i=1;i<nmax;i++)pwr[i]=pwr[i-1]*base%mod;

    mem_pref[0]=1;
    for(int i=1;i<nmax;i++)
    {
        mem_pref[i]=(mem_pref[i-1]+pwr[i])%mod;
    }

    cin>>n;

    for(int i=0;i<3;i++)cin>>inp[i];

    do
    {
        string cur="";

        for(int i=0;i<=5;i++)
        {
            if(i==0)cur=inp[order[i]];
            else
            {
                int other=order[i%3];

                for(int k=0;k<n;k++)
                {
                    if(cur[k]!=inp[other][k])
                    {
                        cur[k]=1LL*'I'+'J'+'O'-cur[k]-inp[other][k];
                    }
                }
            }

            valid.insert(cur);
        }
    }
    while(next_permutation(order,order+3));

    for(auto w:valid)
    {
        long long cur=0;

        for(auto v:w)
            cur=(cur*base+hsh(v))%mod;

        valid_hsh.insert(cur);
    }

    int q;
    cin>>q;

    cin>>t;

    build(1,0,n-1);

    check();

    for(int i=1;i<=q;i++)
    {
        int l,r;
        char c;

        cin>>l>>r>>c;

        update(1,0,n-1,l-1,r-1,hsh(c));

        check();
    }

    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 3984 KB Output is correct
2 Correct 421 ms 4036 KB Output is correct
3 Correct 429 ms 4028 KB Output is correct
4 Correct 397 ms 3916 KB Output is correct
5 Correct 394 ms 4004 KB Output is correct
6 Correct 390 ms 3896 KB Output is correct
7 Correct 396 ms 4040 KB Output is correct
8 Correct 415 ms 3984 KB Output is correct
9 Correct 451 ms 3944 KB Output is correct
10 Correct 476 ms 3932 KB Output is correct
11 Correct 429 ms 4036 KB Output is correct
12 Correct 416 ms 3992 KB Output is correct
13 Correct 420 ms 4036 KB Output is correct
14 Correct 409 ms 4024 KB Output is correct
15 Correct 414 ms 4016 KB Output is correct
16 Correct 417 ms 4036 KB Output is correct
17 Correct 417 ms 3956 KB Output is correct
18 Correct 428 ms 4140 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 3984 KB Output is correct
2 Correct 421 ms 4036 KB Output is correct
3 Correct 429 ms 4028 KB Output is correct
4 Correct 397 ms 3916 KB Output is correct
5 Correct 394 ms 4004 KB Output is correct
6 Correct 390 ms 3896 KB Output is correct
7 Correct 396 ms 4040 KB Output is correct
8 Correct 415 ms 3984 KB Output is correct
9 Correct 451 ms 3944 KB Output is correct
10 Correct 476 ms 3932 KB Output is correct
11 Correct 429 ms 4036 KB Output is correct
12 Correct 416 ms 3992 KB Output is correct
13 Correct 420 ms 4036 KB Output is correct
14 Correct 409 ms 4024 KB Output is correct
15 Correct 414 ms 4016 KB Output is correct
16 Correct 417 ms 4036 KB Output is correct
17 Correct 417 ms 3956 KB Output is correct
18 Correct 428 ms 4140 KB Output is correct
19 Correct 707 ms 17800 KB Output is correct
20 Correct 693 ms 17612 KB Output is correct
21 Correct 577 ms 17628 KB Output is correct
22 Correct 551 ms 17544 KB Output is correct
23 Correct 498 ms 4972 KB Output is correct
24 Correct 487 ms 4804 KB Output is correct
25 Correct 604 ms 17672 KB Output is correct
26 Correct 587 ms 17604 KB Output is correct
27 Correct 693 ms 17752 KB Output is correct
28 Correct 628 ms 17592 KB Output is correct
29 Correct 637 ms 17656 KB Output is correct
30 Correct 519 ms 4964 KB Output is correct
31 Correct 614 ms 17576 KB Output is correct
32 Correct 601 ms 17576 KB Output is correct
33 Correct 491 ms 4748 KB Output is correct
34 Correct 661 ms 17744 KB Output is correct
35 Correct 542 ms 17256 KB Output is correct
36 Correct 551 ms 4828 KB Output is correct
37 Correct 511 ms 4960 KB Output is correct
38 Correct 642 ms 17584 KB Output is correct
39 Correct 536 ms 17616 KB Output is correct
40 Correct 604 ms 11164 KB Output is correct
41 Correct 747 ms 17736 KB Output is correct
42 Correct 383 ms 18060 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 3984 KB Output is correct
2 Correct 421 ms 4036 KB Output is correct
3 Correct 429 ms 4028 KB Output is correct
4 Correct 397 ms 3916 KB Output is correct
5 Correct 394 ms 4004 KB Output is correct
6 Correct 390 ms 3896 KB Output is correct
7 Correct 396 ms 4040 KB Output is correct
8 Correct 415 ms 3984 KB Output is correct
9 Correct 451 ms 3944 KB Output is correct
10 Correct 476 ms 3932 KB Output is correct
11 Correct 429 ms 4036 KB Output is correct
12 Correct 416 ms 3992 KB Output is correct
13 Correct 420 ms 4036 KB Output is correct
14 Correct 409 ms 4024 KB Output is correct
15 Correct 414 ms 4016 KB Output is correct
16 Correct 417 ms 4036 KB Output is correct
17 Correct 417 ms 3956 KB Output is correct
18 Correct 428 ms 4140 KB Output is correct
19 Correct 425 ms 3948 KB Output is correct
20 Correct 466 ms 4000 KB Output is correct
21 Correct 407 ms 4024 KB Output is correct
22 Correct 397 ms 4016 KB Output is correct
23 Correct 413 ms 4116 KB Output is correct
24 Correct 407 ms 3952 KB Output is correct
25 Correct 419 ms 4216 KB Output is correct
26 Correct 392 ms 3988 KB Output is correct
27 Correct 413 ms 4036 KB Output is correct
28 Correct 371 ms 3964 KB Output is correct
29 Correct 426 ms 4068 KB Output is correct
30 Correct 405 ms 3936 KB Output is correct
31 Correct 436 ms 4000 KB Output is correct
32 Correct 436 ms 4168 KB Output is correct
33 Correct 409 ms 3980 KB Output is correct
34 Correct 390 ms 4036 KB Output is correct
35 Correct 407 ms 4036 KB Output is correct
36 Correct 421 ms 4036 KB Output is correct
37 Correct 412 ms 4076 KB Output is correct
38 Correct 413 ms 4056 KB Output is correct
39 Correct 413 ms 4016 KB Output is correct
40 Correct 412 ms 3964 KB Output is correct
41 Correct 444 ms 3964 KB Output is correct
42 Correct 409 ms 4036 KB Output is correct
43 Correct 427 ms 3980 KB Output is correct
44 Correct 420 ms 4036 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 3984 KB Output is correct
2 Correct 421 ms 4036 KB Output is correct
3 Correct 429 ms 4028 KB Output is correct
4 Correct 397 ms 3916 KB Output is correct
5 Correct 394 ms 4004 KB Output is correct
6 Correct 390 ms 3896 KB Output is correct
7 Correct 396 ms 4040 KB Output is correct
8 Correct 415 ms 3984 KB Output is correct
9 Correct 451 ms 3944 KB Output is correct
10 Correct 476 ms 3932 KB Output is correct
11 Correct 429 ms 4036 KB Output is correct
12 Correct 416 ms 3992 KB Output is correct
13 Correct 420 ms 4036 KB Output is correct
14 Correct 409 ms 4024 KB Output is correct
15 Correct 414 ms 4016 KB Output is correct
16 Correct 417 ms 4036 KB Output is correct
17 Correct 417 ms 3956 KB Output is correct
18 Correct 428 ms 4140 KB Output is correct
19 Correct 707 ms 17800 KB Output is correct
20 Correct 693 ms 17612 KB Output is correct
21 Correct 577 ms 17628 KB Output is correct
22 Correct 551 ms 17544 KB Output is correct
23 Correct 498 ms 4972 KB Output is correct
24 Correct 487 ms 4804 KB Output is correct
25 Correct 604 ms 17672 KB Output is correct
26 Correct 587 ms 17604 KB Output is correct
27 Correct 693 ms 17752 KB Output is correct
28 Correct 628 ms 17592 KB Output is correct
29 Correct 637 ms 17656 KB Output is correct
30 Correct 519 ms 4964 KB Output is correct
31 Correct 614 ms 17576 KB Output is correct
32 Correct 601 ms 17576 KB Output is correct
33 Correct 491 ms 4748 KB Output is correct
34 Correct 661 ms 17744 KB Output is correct
35 Correct 542 ms 17256 KB Output is correct
36 Correct 551 ms 4828 KB Output is correct
37 Correct 511 ms 4960 KB Output is correct
38 Correct 642 ms 17584 KB Output is correct
39 Correct 536 ms 17616 KB Output is correct
40 Correct 604 ms 11164 KB Output is correct
41 Correct 747 ms 17736 KB Output is correct
42 Correct 383 ms 18060 KB Output is correct
43 Correct 425 ms 3948 KB Output is correct
44 Correct 466 ms 4000 KB Output is correct
45 Correct 407 ms 4024 KB Output is correct
46 Correct 397 ms 4016 KB Output is correct
47 Correct 413 ms 4116 KB Output is correct
48 Correct 407 ms 3952 KB Output is correct
49 Correct 419 ms 4216 KB Output is correct
50 Correct 392 ms 3988 KB Output is correct
51 Correct 413 ms 4036 KB Output is correct
52 Correct 371 ms 3964 KB Output is correct
53 Correct 426 ms 4068 KB Output is correct
54 Correct 405 ms 3936 KB Output is correct
55 Correct 436 ms 4000 KB Output is correct
56 Correct 436 ms 4168 KB Output is correct
57 Correct 409 ms 3980 KB Output is correct
58 Correct 390 ms 4036 KB Output is correct
59 Correct 407 ms 4036 KB Output is correct
60 Correct 421 ms 4036 KB Output is correct
61 Correct 412 ms 4076 KB Output is correct
62 Correct 413 ms 4056 KB Output is correct
63 Correct 413 ms 4016 KB Output is correct
64 Correct 412 ms 3964 KB Output is correct
65 Correct 444 ms 3964 KB Output is correct
66 Correct 409 ms 4036 KB Output is correct
67 Correct 427 ms 3980 KB Output is correct
68 Correct 420 ms 4036 KB Output is correct
69 Correct 668 ms 18804 KB Output is correct
70 Correct 738 ms 19256 KB Output is correct
71 Correct 488 ms 4872 KB Output is correct
72 Correct 489 ms 4876 KB Output is correct
73 Correct 487 ms 4832 KB Output is correct
74 Correct 557 ms 17728 KB Output is correct
75 Correct 496 ms 4924 KB Output is correct
76 Correct 608 ms 18088 KB Output is correct
77 Correct 572 ms 17876 KB Output is correct
78 Correct 495 ms 4912 KB Output is correct
79 Correct 493 ms 4964 KB Output is correct
80 Incorrect 553 ms 18400 KB Output isn't correct
81 Halted 0 ms 0 KB -