Submission #1189176

#TimeUsernameProblemLanguageResultExecution timeMemory
1189176alexddCrossing (JOI21_crossing)C++20
26 / 100
7073 ms16472 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MOD = 1e9+9; int n,q; string s[3]; string combine(string a, string b) { assert(a.size() == b.size()); string aux; aux.resize(a.size()); for(int i=0;i<a.size();i++) { if(a[i]==b[i]) { aux[i] = a[i]; } else { for(char ch:{'J','O','I'}) if(ch!=a[i] && ch!=b[i]) aux[i] = ch; } } return aux; } map<pair<int,int>,int> mp; int p[200005][2],prefp[200005][2]; int aint[800005][2]; char lazy[800005]; string t; void build(int nod, int st, int dr) { if(st==dr) { aint[nod][0] = p[st][0] * t[st-1]%MOD; aint[nod][1] = p[st][1] * t[st-1]%MOD; return; } int mij=(st+dr)/2; build(nod*2,st,mij); build(nod*2+1,mij+1,dr); aint[nod][0] = (aint[nod*2][0] + aint[nod*2+1][0])%MOD; aint[nod][1] = (aint[nod*2][1] + aint[nod*2+1][1])%MOD; } int calchsh(int st, int dr, char val, int c) { return (prefp[dr][c] - prefp[st-1][c] + MOD) * val%MOD; } void propagate(int nod, int st, int dr) { if(!lazy[nod]) return; int mij=(st+dr)/2; lazy[nod*2] = lazy[nod*2+1] = lazy[nod]; for(int c=0;c<2;c++) { aint[nod*2][c] = calchsh(st,mij,lazy[nod],c); aint[nod*2+1][c] = calchsh(mij+1,dr,lazy[nod],c); } lazy[nod]=0; } void upd(int nod, int st, int dr, int le, int ri, char newv) { if(le>ri) return; if(le==st && dr==ri) { lazy[nod] = newv; aint[nod][0] = calchsh(st,dr,newv,0); aint[nod][1] = calchsh(st,dr,newv,1); return; } propagate(nod,st,dr); int mij=(st+dr)/2; upd(nod*2,st,mij,le,min(mij,ri),newv); upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv); aint[nod][0] = (aint[nod*2][0] + aint[nod*2+1][0])%MOD; aint[nod][1] = (aint[nod*2][1] + aint[nod*2+1][1])%MOD; } signed main() { ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>s[0]>>s[1]>>s[2]; p[0][0] = p[0][1] = 1; p[1][0] = 31; p[1][1] = 29; for(int i=2;i<=n;i++) { p[i][0] = p[i-1][0]*p[1][0]%MOD; p[i][1] = p[i-1][1]*p[1][1]%MOD; } for(int i=1;i<=n;i++) { prefp[i][0] = (prefp[i-1][0] + p[i][0])%MOD; prefp[i][1] = (prefp[i-1][1] + p[i][1])%MOD; } for(int ord=0;ord<3;ord++) { for(int mask=1;mask<(1<<3);mask++) { string idk; bool gol=1; for(int i=0;i<3;i++) { if((1<<i)&mask) { if(gol) { gol = 0; idk = s[i]; } else { idk = combine(idk, s[i]); } } } assert(!gol); t = idk; build(1,1,n); mp[{aint[1][0],aint[1][1]}]=1; } swap(s[0],s[1]); swap(s[0],s[2]); } cin>>q; cin>>t; build(1,1,n); if(mp[{aint[1][0],aint[1][1]}]) cout<<"Yes\n"; else cout<<"No\n"; while(q--) { int le,ri; char ch; cin>>le>>ri>>ch; le--; ri--; for(int i=le;i<=ri;i++) t[i] = ch; build(1,1,n); if(mp[{aint[1][0],aint[1][1]}]) cout<<"Yes\n"; else cout<<"No\n"; } return 0; } /* 4 JOJO JJOI OJOO 3 IJOJ 1 4 O 2 2 J 2 4 I */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...