Submission #423208

#	Time	Username	Problem	Language	Result	Execution time	Memory
423208		MKopchev	Crossing (JOI21_crossing)	C++14	100 / 100	767 ms	19492 KiB

Main

#include<bits/stdc++.h>
using namespace std;

const int base=23,mod=1e9+9,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 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51