Submission #1299651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299651		trandangquang	Crossing (JOI21_crossing)	C++20	100 / 100	3505 ms	24288 KiB

Main

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

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define fi first
#define se second
#define ll long long
#define eb emplace_back
#define pb push_back
#define __builtin_popcount __builtin_popcountll
#define _ << " " <<

template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}

const int mod[] = {(int)1e9+7, (int)1e9+9, (int)1e9+21};
const int numMod=1;

struct Hash{
    int a[3];
    Hash(){
        a[0]=a[1]=a[2]=0;
    }
    Hash(int x){
        rep(i,numMod) a[i]=x%mod[i];
    }
    void print(){
        rep(i,numMod) cout<<a[i]<<" ";
        cout<<'\n';
    }
    Hash operator * (int x) const {
        Hash res;
        rep(i,numMod) res.a[i]=(1LL*a[i]*x) % mod[i];
        return res;
    }
    Hash operator + (int x) const {
        Hash res;
        rep(i,numMod){
            res.a[i]=a[i]+x;
            if(res.a[i]>=mod[i]) res.a[i]-=mod[i];
        }
        return res;
    }
    Hash operator * (const Hash &x) const {
        Hash res;
        rep(i,numMod) res.a[i]=(1LL*a[i]*x.a[i]) % mod[i];
        return res;
    }
    Hash operator + (const Hash &x) const {
        Hash res;
        rep(i,numMod){
            res.a[i]=a[i]+x.a[i];
            if(res.a[i]>=mod[i]) res.a[i]-=mod[i];
        }
        return res;
    }
    bool operator == (const Hash &x) const {
        rep(i,numMod){
            if(a[i]!=x.a[i]) return false;
        }
        return true;
    }
};

int q;
string initT;
vector<Hash> hs;
map<string,int> mp;
vector<string> gens;
string in1[3],in2[3],in3[3];

string comb(string a, string b){
    assert(sz(a)==sz(b));
    string res;
    rep(i,sz(a)){
        if(a[i]==b[i]) res=res+a[i];
        else{
            res=res+char((int)a[i]^(int)b[i]^'J'^'O'^'I');
        }
    }
    return res;
}
void generate(){
    in2[0]=comb(in1[1],in1[2]);
    in2[1]=comb(in1[0],in1[2]);
    in2[2]=comb(in1[0],in1[1]);

    in3[0]=comb(in2[0],in1[0]);
    in3[1]=comb(in2[1],in1[1]);
    in3[2]=comb(in2[2],in1[2]);

    rep(i,3){
        mp[in1[i]]++;
        mp[in2[i]]++;
        mp[in3[i]]++;
    }
    for(auto i:mp) gens.eb(i.fi);
}

const int N=2e5+5;

int n;
Hash pw[N],tot[N];

struct SegmentTree{
    #define lc id<<1
    #define rc id<<1|1

    Hash st[N<<2]; int lz[N<<2];
    SegmentTree(){
        fill(begin(st),end(st),Hash());
        fill(begin(lz),end(lz),-1);
    }

    void build(int id=1, int l=0, int r=n-1){
        if(l==r){
            st[id]=Hash(initT[l]-'A');
            return;
        }
        int mid=(l+r)>>1;
        build(lc,l,mid);
        build(rc,mid+1,r);
        st[id]=st[lc]*pw[r-mid]+st[rc];
    }
    void apply(int id, int val, int len){
        st[id]=tot[len-1]*val;
        lz[id]=val;
    }
    void down(int id, int len1, int len2){
        if(lz[id]==-1) return;
        apply(lc,lz[id],len1);
        apply(rc,lz[id],len2);
        lz[id]=-1;
    }
    void upd(int u, int v, int val, int id=1, int l=0, int r=n-1){
        if(u>r||v<l) return;
        if(u<=l&&r<=v){
            apply(id,val,r-l+1);
            return;
        }
        int mid=(l+r)>>1;
        down(id,mid-l+1,r-mid);
        upd(u,v,val,lc,l,mid);
        upd(u,v,val,rc,mid+1,r);
        st[id]=st[lc]*pw[r-mid]+st[rc];
    }
} smt;

void buildHash(){
    hs.resize(sz(gens));
    rep(i,sz(gens)){
        rep(j,sz(gens[i])){
            hs[i]=hs[i]*31 + (int)(gens[i][j]-'A');
        }
//        hs[i].print();
    }

    pw[0]=Hash(1);
    foru(i,1,n) pw[i]=pw[i-1]*31;
    tot[0]=pw[0];
    foru(i,1,n) tot[i]=tot[i-1]+pw[i];
    smt.build();
//    smt.st[1].print();
}

void solve(){
    cin>>n;
    rep(i,3) cin>>in1[i];
    generate();

    cin>>q>>initT;
    buildHash();

    bool chk=0;
    rep(i,sz(hs)){
        if(hs[i]==smt.st[1]) chk=1;
    }
    cout<<(chk?"Yes":"No")<<'\n';

    foru(qq,1,q){
        int l,r; char c; cin>>l>>r>>c; --l,--r;
        smt.upd(l,r,c-'A');

        bool chk=0;
        rep(i,sz(hs)){
            if(hs[i]==smt.st[1]) chk=1;
        }
        cout<<(chk?"Yes":"No")<<'\n';
    }
}

int32_t main(){
    #define task "test"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    int tc=1; //cin>>tc;
    foru(i,1,tc){
        solve();
    }
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:203:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  203 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:204:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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