Submission #551530

#	Time	Username	Problem	Language	Result	Execution time	Memory
551530		dungnguyenn_05	Crossing (JOI21_crossing)	C++17	100 / 100	302 ms	18292 KiB

Main

#include<bits/stdc++.h>
#define fs first
#define sc second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
const ll mod=1e9+3,N=200005;

ll n,q,h[10],t[N<<2],lz[N<<2],p[N],pre[N];
string s[10],cur;
char c[5]={'J','O','I'};

string xr(string a,string b)
{
    string res="";
    for(int i=0;i<n;i++)
    {
        if(a[i]==b[i])
        {
            res+=a[i];
            continue;
        }
        for(int j=0;j<3;j++)
            if(c[j]!=a[i] and c[j]!=b[i])
            {
                res+=c[j];
                break;
            }
    }
    return res;
}

void process()
{

    pre[0]=p[0]=1;
    for(int i=1;i<=n;i++)
    {
        p[i]=(p[i-1]*31)%mod;
        pre[i]=(pre[i-1]+p[i])%mod;
    }

    for(int pos=1;pos<=9;pos++)
        for(int i=0;i<n;i++)
            h[pos]=(h[pos]+(s[pos][i]-'A')*p[i])%mod;

}

void down(int node,int l,int r)
{
    if(!lz[node]) return;
    t[node]=(pre[r-l]*lz[node])%mod;
    if(l!=r)
    {
        lz[node<<1]=lz[node];
        lz[node<<1|1]=lz[node];
    }
    lz[node]=0;
}

void upd(int u,int v,int val,int node=1,int l=1,int r=n)
{
    down(node,l,r);
    if(u>r or v<l or l>r) return;
    if(u<=l and r<=v)
    {
        lz[node]=val;
        down(node,l,r);
        return;
    }
    int mid=(l+r)>>1;
    upd(u,v,val,node<<1,l,mid);
    upd(u,v,val,node<<1|1,mid+1,r);
    t[node]=(t[node<<1]+t[node<<1|1]*p[mid-l+1])%mod;
}

ll get()
{
    down(1,1,n);
    return t[1];
}

bool avail()
{
    ll val=get();
    for(int pos=1;pos<=9;pos++)
        if(val==h[pos])
            return 1;

    return 0;
}

void solve()
{
    cin>>n>>s[1]>>s[2]>>s[3];
    s[4]=xr(s[1],s[2]);
    s[5]=xr(s[1],s[3]);
    s[6]=xr(s[2],s[3]);
    s[7]=xr(s[3],s[4]);
    s[8]=xr(s[2],s[5]);
    s[9]=xr(s[1],s[6]);

    process();

    cin>>q>>cur;
    cur=' '+cur;
    for(int i=1;i<=n;i++)
        upd(i,i,cur[i]-'A');

    if(avail())
        cout<<"Yes\n";
    else
        cout<<"No\n";

    while(q--)
    {
        int l,r; char c;
        cin>>l>>r>>c;
        upd(l,r,c-'A');
        if(avail())
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }



}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);  
    int test=1;
    // cin>>test;
    while(test--)
        solve();
}

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