Submission #1150653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150653		fatman87878	Crossing (JOI21_crossing)	C++20	100 / 100	485 ms	13860 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

constexpr int maxN=2e5+5,mod = 1e9+7,C = 777771449;

int n,q,tag[maxN],pw[maxN];

map<char,int> mp;

map<int,int> hashs;

vector<string> gaba;

struct NODE{
    int val,len,unithash;
    friend NODE operator+(NODE l,NODE r){
        NODE ret{};
        ret.val = (l.val + pw[l.len]*1ll*r.val)%mod;
        ret.len = l.len+r.len;
        ret.unithash = (l.unithash + pw[l.len]*1ll*r.unithash)%mod;
        return ret;
    }
}segt[maxN<<1];

inline void upd(int pos,int tgw){
    segt[pos].val = tgw*1ll*segt[pos].unithash%mod;
    if(pos<n)tag[pos] = tgw;
}

inline void push(int pos){
    pos+=n;
    for(int h = __lg(n);h;h--){
        int i = pos>>h;
        if(!i)continue;
        if(tag[i])upd(i<<1,tag[i]),upd(i<<1|1,tag[i]),tag[i] = 0;
    }
}

inline void pull(int pos){
    for(pos+=n;pos>>=1;)if(!tag[pos])segt[pos] = segt[pos<<1] + segt[pos<<1|1];
}

inline void mdf(int _l,int _r,int tgw){
    push(_l),push(_r-1);
    for(int l = _l+n,r = _r+n;l<r;l>>=1,r>>=1){
        if(l&1)upd(l++,tgw);
        if(r&1)upd(--r,tgw);
    }
    pull(_l),pull(_r-1);
}

inline int query(){
    push(0),push(n-1);
    NODE retl = {0,0,0},retr = {0,0,0};
    for(int l = n,r = 2*n;l<r;l>>=1,r>>=1){
        if(l&1)retl = retl + segt[l++];
        if(r&1)retr = segt[--r] + retr;
    }
    return (retl+retr).val;
}

inline void report(){
    cout<<(hashs.count(query())?"Yes\n":"No\n");
}

inline void dfs(string& s){
    for(int i = 0,sz = gaba.size();i<sz;i++){
        string pp = gaba[i];
        string nxt = "";
        int hash = 0;
        for(int j = 0;j<n;j++){
            char c;
            if(s[j]==pp[j])c=s[j];
            else {
                for(char a:{'J','O','I'})if(s[j]!=a&&pp[j]!=a)c=a;
            }
            nxt.push_back(c);
            hash+=pw[j]*1ll*mp[c]%mod;
            if(hash>=mod)hash-=mod;
        }
        if(!hashs.count(hash)){
            hashs[hash]=1;
            gaba.emplace_back(nxt);
            dfs(nxt);
        }
    }
}

int main(){
    IOS
    cin>>n;
    pw[0] = 1;
    for(int i = 1;i<n;i++)pw[i]=pw[i-1]*1ll*C%mod;
    mp['J']=1;
    mp['O']=2;
    mp['I']=3;
    string a,b,c;
    cin>>a>>b>>c;
    gaba.emplace_back(a);
    gaba.emplace_back(b);
    gaba.emplace_back(c);
    dfs(a);
    dfs(b);
    dfs(c);
    cin>>q;
    string t;cin>>t;
    for(int i = 0;i<n;i++){
        segt[i+n].val=mp[t[i]];
        segt[i+n].len=1;
        segt[i+n].unithash=1;
    }
    for(int i = n;--i;)segt[i] = segt[i<<1] + segt[i<<1|1];
    report();
    for(int l,r;q--;){
        char c;
        cin>>l>>r>>c,--l;
        mdf(l,r,mp[c]);
        report();
    }
}

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