Submission #881390

#	Time	Username	Problem	Language	Result	Execution time	Memory
881390		1L1YA	Crossing (JOI21_crossing)	C++17	100 / 100	526 ms	34200 KiB

Main

//1L1YA
#include<bits/stdc++.h>
using namespace std;
#define ll           long long
#define Pb           push_back
#define dokme(x)     cout << x << endl, exit(0)
#define pii          pair<int,int>
#define F            first
#define S            second
#define endl         '\n'
#define sep          ' '
#define all(x)       x.begin(),x.end()
#define FastIO       ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lc           id<<1
#define rc           lc|1

const ll mod=1e9+9;
const ll oo=4e18;
const int N=2e5+5;
const int lg=23;
const int base=111;

ll n,q,h[3][3][N],hsh[4][N],lz[N<<2],seg[N<<2];
string t,s[3][3];

ll Pow(ll a,ll b){
    ll ans=1;
    for(;b;b>>=1,a=a*a%mod)
        if(b&1)
            ans=ans*a%mod;
    return ans;
}

ll inv(ll x){
    return Pow(x,mod-2);
}

void change(string &s){
    for(int i=1;i<=n;i++)
        if(s[i]=='J')
            s[i]='b';
        else if(s[i]=='O')
            s[i]='c';
        else
            s[i]='d';
}

void shift(int id,int l,int r){
    if(!lz[id])
        return;
    int mid=l+r>>1;
    seg[lc]=hsh[lz[id]][mid-l];lz[lc]=lz[id];
    seg[rc]=hsh[lz[id]][r-mid];lz[rc]=lz[id];
    lz[id]=0;
}

void update(int ql,int qr,int val,int id=1,int l=1,int r=n+1){
    if(qr<=l || ql>=r)    return;
    if(ql<=l && r<=qr){
        seg[id]=hsh[val][r-l];
        lz[id]=val;
        return;
    }
    int mid=l+r>>1;
    shift(id,l,r);
    update(ql,qr,val,lc,l,mid);
    update(ql,qr,val,rc,mid,r);
    seg[id]=(seg[lc]*Pow(base,r-mid)%mod+seg[rc])%mod;
}

int main(){
    FastIO

    cin >> n >> s[0][0] >> s[0][1] >> s[0][2];
    s[0][0]='#'+s[0][0];s[0][1]='#'+s[0][1];s[0][2]='#'+s[0][2];
    change(s[0][0]);change(s[0][1]);change(s[0][2]);
    for(int k=1;k<3;k++){
        s[k][0]=s[k-1][0];s[k][1]=s[k-1][1];s[k][2]=s[k-1][2];
        for(int i=1;i<=n;i++){
            if(s[k-1][1][i]==s[k-1][2][i])
                s[k][0][i]=s[k-1][1][i];
            else{
                s[k][0][i]=(char)(((s[k-1][1][i]-'a')^(s[k-1][2][i]-'a'))+'a');
            }
            if(s[k-1][0][i]==s[k-1][2][i])
                s[k][1][i]=s[k-1][0][i];
            else{
                s[k][1][i]=(char)(((s[k-1][0][i]-'a')^(s[k-1][2][i]-'a'))+'a');
            }
            if(s[k-1][1][i]==s[k-1][0][i])
                s[k][2][i]=s[k-1][1][i];
            else{
                s[k][2][i]=(char)(((s[k-1][1][i]-'a')^(s[k-1][0][i]-'a'))+'a');
            }
        }
    }
    for(int j=1;j<=3;j++)
        for(int i=1;i<=n;i++)
            hsh[j][i]=(hsh[j][i-1]*base+j)%mod;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            for(int k=1;k<=n;k++)
                h[i][j][k]=(h[i][j][k-1]*base+s[i][j][k]-'a')%mod;
    cin >> q >> t;
    bool fl=0;
    t='#'+t;
    change(t);
    for(int i=1;i<=n;i++)
        update(i,i+1,t[i]-'a');
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)    
            if(seg[1]==h[i][j][n])
                fl=1;
    if(fl)    cout << "Yes" << endl;
    else    cout << "No" << endl;
    while(q--){
        int l,r;
        char c;
        cin >> l >> r >> c;
        if(c=='J')    c='b';
        else if(c=='O')    c='c';
        else    c='d';
        update(l,r+1,c-'a');
        fl=0;
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                if(seg[1]==h[i][j][n])
                    fl=1;
        if(fl)    cout << "Yes" << endl;
        else    cout << "No" << endl;
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void shift(int, int, int)':
Main.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid=l+r>>1;
      |             ~^~
Main.cpp: In function 'void update(int, int, int, int, int, int)':
Main.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |     int mid=l+r>>1;
      |             ~^~

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