Submission #1189177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189177		alexdd	Crossing (JOI21_crossing)	C++20	100 / 100	324 ms	29224 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+9;
int n,q;
string s[3];
string combine(string a, string b)
{
    assert(a.size() == b.size());
    string aux;
    aux.resize(a.size());
    for(int i=0;i<a.size();i++)
    {
        if(a[i]==b[i])
        {
            aux[i] = a[i];
        }
        else
        {
            for(char ch:{'J','O','I'})
                if(ch!=a[i] && ch!=b[i])
                    aux[i] = ch;
        }
    }
    return aux;
}
map<pair<int,int>,int> mp;

int p[200005][2],prefp[200005][2];

int aint[800005][2];
char lazy[800005];
string t;
void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod][0] = p[st][0] * t[st-1]%MOD;
        aint[nod][1] = p[st][1] * t[st-1]%MOD;
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    aint[nod][0] = (aint[nod*2][0] + aint[nod*2+1][0])%MOD;
    aint[nod][1] = (aint[nod*2][1] + aint[nod*2+1][1])%MOD;
}
int calchsh(int st, int dr, char val, int c)
{
    return (prefp[dr][c] - prefp[st-1][c] + MOD) * val%MOD;
}
void propagate(int nod, int st, int dr)
{
    if(!lazy[nod])
        return;
    int mij=(st+dr)/2;
    lazy[nod*2] = lazy[nod*2+1] = lazy[nod];
    for(int c=0;c<2;c++)
    {
        aint[nod*2][c] = calchsh(st,mij,lazy[nod],c);
        aint[nod*2+1][c] = calchsh(mij+1,dr,lazy[nod],c);
    }
    lazy[nod]=0;
}
void upd(int nod, int st, int dr, int le, int ri, char newv)
{
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        lazy[nod] = newv;
        aint[nod][0] = calchsh(st,dr,newv,0);
        aint[nod][1] = calchsh(st,dr,newv,1);
        return;
    }
    propagate(nod,st,dr);
    int mij=(st+dr)/2;
    upd(nod*2,st,mij,le,min(mij,ri),newv);
    upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv);
    aint[nod][0] = (aint[nod*2][0] + aint[nod*2+1][0])%MOD;
    aint[nod][1] = (aint[nod*2][1] + aint[nod*2+1][1])%MOD;
}

signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>s[0]>>s[1]>>s[2];
    p[0][0] = p[0][1] = 1;
    p[1][0] = 31;
    p[1][1] = 29;
    for(int i=2;i<=n;i++)
    {
        p[i][0] = p[i-1][0]*p[1][0]%MOD;
        p[i][1] = p[i-1][1]*p[1][1]%MOD;
    }
    for(int i=1;i<=n;i++)
    {
        prefp[i][0] = (prefp[i-1][0] + p[i][0])%MOD;
        prefp[i][1] = (prefp[i-1][1] + p[i][1])%MOD;
    }
    for(int ord=0;ord<3;ord++)
    {
        for(int mask=1;mask<(1<<3);mask++)
        {
            string idk;
            bool gol=1;
            for(int i=0;i<3;i++)
            {
                if((1<<i)&mask)
                {
                    if(gol)
                    {
                        gol = 0;
                        idk = s[i];
                    }
                    else
                    {
                        idk = combine(idk, s[i]);
                    }
                }
            }
            assert(!gol);
            t = idk;
            build(1,1,n);
            mp[{aint[1][0],aint[1][1]}]=1;
        }
        swap(s[0],s[1]);
        swap(s[0],s[2]);
    }

    cin>>q;
    cin>>t;
    build(1,1,n);
    if(mp[{aint[1][0],aint[1][1]}])
        cout<<"Yes\n";
    else
        cout<<"No\n";
    while(q--)
    {
        int le,ri;
        char ch;
        cin>>le>>ri>>ch;

        upd(1,1,n,le,ri,ch);

        if(mp[{aint[1][0],aint[1][1]}])
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }
    return 0;
}
/*

4
JOJO
JJOI
OJOO
3
IJOJ
1 4 O
2 2 J
2 4 I


*/

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51