Submission #705064

#TimeUsernameProblemLanguageResultExecution timeMemory
705064MtSakaCrossing (JOI21_crossing)C++17
0 / 100
344 ms8784 KiB
#include<bits/stdc++.h> #define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++) #define rrep(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;i--) using ll=long long; using namespace std; using ull=unsigned long long; vector<ull>pw(400000),pw2(400000); static constexpr ull MOD=(1LL<<61)-1; static constexpr ull inv2=(1LL<<60); static constexpr ull base=2199866433; ull mul(ull a,ull b){ return __uint128_t(a)*b%MOD; } ull add(ull a,ull b){ a+=b;if(a>=MOD)a-=MOD; return a; } ull div2(ull a){ return mul(a,inv2); } void init(){ pw[0]=1; rep(i,1,pw.size())pw[i]=mul(base,pw[i-1]); pw2[0]=0; rep(i,1,pw2.size())pw2[i]=pw2[i-1]+pw[i-1]; } int get_id(char c){ if(c=='J')return 0; if(c=='O')return 1; return 2; } char from_id(int a){ if(a==0)return 'J'; if(a==1)return 'O'; return 'I'; } struct segment_rolling_hash{ private: int n,sz,lg; vector<pair<ull,ll>>seg; vector<int>lazy; void all_apply(int k,int a){ seg[k].first=mul(from_id(a),pw2[seg[k].second]); if(k<sz)lazy[k]=a; } void push(int k){ if(lazy[k]==-1)return; all_apply(k<<1,lazy[k]);all_apply(k<<1|1,lazy[k]); lazy[k]=-1; } void update(int i){ seg[i].first=add(mul(seg[i<<1].first,pw[seg[i<<1|1].second]),seg[i<<1|1].first); seg[i].second=seg[i<<1].second+seg[i<<1|1].second; } public: segment_rolling_hash(string s):n(s.size()){ sz=1,lg=0; while(sz<n)sz<<=1,lg++; seg.resize(sz<<1); rep(i,0,n){ seg[i+sz].second=1; seg[i+sz].first=s[i]; } rrep(i,1,sz)update(i); lazy.assign(sz,-1); } void apply(int l,int r,int a){ l+=sz,r+=sz; rrep(i,1,lg+1){ if(((l>>i)<<i)!=l)push(l>>i); if(((r>>i)<<i)!=r)push((r-1)>>i); } for(int l2=l,r2=r;l2<r2;l2>>=1,r2>>=1){ if(l2&1)all_apply(l2++,a); if(r2&1)all_apply(--r2,a); } rep(i,0,lg+1){ if(((l>>i)<<i)!=l)update(l>>i); if(((r>>i)<<i)!=r)update((r-1)>>i); } } ull all_prod()const{return seg[1].first;} }; ull get_hash(string a){ ull hash=0; for(auto i:a){ hash=mul(hash,base); hash=add(hash,i); } return hash; } string f(string a,string b){ assert(a.size()==b.size()); string ans(a.size(),'1'); rep(i,0,a.size()){ if(get_id(a[i])==get_id(b[i]))ans[i]=a[i]; else ans[i]=from_id(3^get_id(a[i])^get_id(b[i])); } return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); init(); int n;cin>>n; string a,b,c;cin>>a>>b>>c; //cerr<<a<<" "<<b<<" "<<c<<endl; string ab=f(a,b),bc=f(b,c),ac=f(a,c),abbc=f(ab,bc),abac=f(ab,ac),bcac=f(bc,ac); //cerr<<ab<<" "<<bc<<" "<<ac<<endl; //cerr<<abbc<<" "<<abac<<" "<<bcac<<endl; set<ull>st; st.insert(get_hash(a)); st.insert(get_hash(b)); st.insert(get_hash(c)); st.insert(get_hash(ab)); st.insert(get_hash(bc)); st.insert(get_hash(ac)); st.insert(get_hash(abbc)); st.insert(get_hash(abac)); st.insert(get_hash(bcac)); //for(auto i:st)cerr<<i<<endl; int q;cin>>q; string t;cin>>t; segment_rolling_hash seg(t); if(st.count(seg.all_prod())){ cout<<"Yes"<<endl; } else cout<<"No"<<endl; rep(i,0,q){ int l,r;char c; cin>>l>>r>>c; l--; seg.apply(l,r,get_id(c)); //cerr<<seg.all_prod()<<endl; if(st.count(seg.all_prod())){ cout<<"Yes"<<endl; } else cout<<"No"<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...