Submission
# | When | Author | Problem | Language | CPU | Memory | |
---|---|---|---|---|---|---|---|
3627 | 2021-12-22 00:50:04 | ewu_ieee21_user_34 | Range Equal Query | C++ 11 | 15 ms | 3496 kb | Wrong Answer - 4 |
Test Cases
# | CPU | Memory | Points | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
1 | 3 ms | 3492 kb | 1 | Accepted | |||||||
2 | 3 ms | 3496 kb | 1 | Accepted | |||||||
3 | 3 ms | 3488 kb | 1 | Accepted | |||||||
4 | 15 ms | 3404 kb | 0 | Wrong Answer | |||||||
5 | 0 ms | 0 kb | 0 | Skipped | |||||||
6 | 0 ms | 0 kb | 0 | Skipped | |||||||
7 | 0 ms | 0 kb | 0 | Skipped | |||||||
8 | 0 ms | 0 kb | 0 | Skipped | |||||||
9 | 0 ms | 0 kb | 0 | Skipped | |||||||
10 | 0 ms | 0 kb | 0 | Skipped | |||||||
11 | 0 ms | 0 kb | 0 | Skipped | |||||||
12 | 0 ms | 0 kb | 0 | Skipped | |||||||
13 | 0 ms | 0 kb | 0 | Skipped | |||||||
14 | 0 ms | 0 kb | 0 | Skipped | |||||||
15 | 0 ms | 0 kb | 0 | Skipped | |||||||
16 | 0 ms | 0 kb | 0 | Skipped | |||||||
17 | 0 ms | 0 kb | 0 | Skipped | |||||||
18 | 0 ms | 0 kb | 0 | Skipped | |||||||
19 | 0 ms | 0 kb | 0 | Skipped | |||||||
20 | 0 ms | 0 kb | 0 | Skipped |
Source Code
#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template <typename num_t> using ordered_set = tree<num_t,null_type,less<num_t>,rb_tree_tag,tree_order_statistics_node_update>; const int DEBUGGER = 0; #define io ios_base::sync_with_stdio(0); cin.tie(NULL) #define mset(a,v) memset(a,v,sizeof(a)) #define lp(i,a,n) for(int i=a;i<n;i++) #define lpr(i,a,n) for(int i=n-1;i>=a;i--) #define stlp(it,stl) for(__typeof(stl.begin()) it=stl.begin();it!=stl.end();it++) #define stlpr(it,stl) for(__typeof(stl.rbegin()) it=stl.rbegin();it!=stl.rend();it++) #define r(a) a.begin(),a.end() #define II ({ ll TEMP; cin>>TEMP; TEMP; }) #define SI ({ string TEMP; cin>>TEMP; TEMP; }) #define AI(a) ({ int n=sizeof(a)/sizeof(a[0]); lp(I,0,n)a[I]=II; }) #define AO(a) ({ int n=sizeof(a)/sizeof(a[0]); lp(I,0,n){cout<<(I?" ":"")<<a[I];} if(DEBUGGER)cout<<endl;else cout<<'\n'; }) #define VI(v) ({ lp(I,0,v.size())v[I]=II; }) #define VO(v) ({ lp(I,0,v.size()){cout<<(I?" ":"")<<v[I];} if(DEBUGGER)cout<<endl;else cout<<'\n'; }) #define outa(a) ({ if(DEBUGGER)dbg(a); else cout<<a<<'\n'; }) #define dbg(a) ({ if(DEBUGGER)cout<<#a<<" = "<<a<<endl; }) #define cbit(n,p) ((n)&(1LL<<(p))) #define sbit(n,p) ((n)|(1LL<<(p))) #define tbit(n,p) ((n)^(1LL<<(p))) #define F first #define S second typedef long long ll; typedef pair<ll,ll> pll; typedef vector<ll> vl; const ll MAX = 1e5+5; const ll MOD = 1e9+7; const ll MOD2 = 1e9+9; const ll INF = 9e18; const double PI = 3.141592653589793238462; ll addM(ll a,ll b){return (a+=b)>=MOD?(a-=MOD):a;} ll subM(ll a,ll b){return (a-=b)<0?(a+=MOD):a;} ll n,m,len,ps[320],ps2[320],pr=110017,pr2=110023; pll blc[320],blc2[320]; vl a,b,blcvl[320]; ll bigMOD(ll a,ll x,ll MOD){ if(x==0)return 1; if(x==1 || a<=1)return a%MOD; ll r=bigMOD(a,x/2,MOD); r=(r*r)%MOD; if(x&1) r=(r*a)%MOD; return r; } pll hashval(vl v){ pll ans={0,0}; ll p_pow=1; lp(i,0,v.size()){ ans.F=(ans.F+v[i]*p_pow)%MOD; p_pow=(p_pow*pr)%MOD; } p_pow=1; lp(i,0,v.size()){ ans.S=(ans.S+v[i]*p_pow)%MOD2; p_pow=(p_pow*pr2)%MOD2; } return ans; } void init(){ for(int i=0;i<n;i+=len){ vl ax; lp(k,i,min(i+len,n)) ax.push_back(a[k]); vl bx; lp(k,i,min(i+len,m)) bx.push_back(b[k]); blc[i/len]=hashval(ax); blcvl[i/len]=ax; blc2[i/len]=hashval(bx); } } void update(int i,int val){ int c_i=i/len; blcvl[c_i][i%len]=val; blc[c_i]=hashval(blcvl[c_i]); a[i]=val; } ll rv(ll i,ll j,int c,int d){ ll sz=j-i+1; if(!sz)return 0; if(c){ if(d) return blc[i/len].F%ps[sz]; else return blc[i/len].S%ps2[sz]; } if(d) return (blc[i/len].F*bigMOD(ps[len-sz],MOD-2,MOD))%MOD; else return (blc[i/len].S*bigMOD(ps2[len-sz],MOD2-2,MOD2))%MOD2; } bool query(int l,int r){ bool ans=1; int c_l=l/len,c_r=r/len; if(c_l==c_r){ for(int i=l,j=0;i<=r;i++,j++) ans&=(a[i]==b[j]); } else{ int j=0; for(int i=l, l_end=(c_l+1)*len-1;i<=l_end;i++,j++){ ans&=a[i]==b[j]; } dbg(ans); for(int i=c_l+1;i<=c_r-1;i++,j+=len){ ll in1=j; ll in2=((j/len)+1)*len-1; ll in3=j+len-1; ll hs=(((rv(in1,in2,1,0)*ps[in2-in1+1])%MOD)+rv(in2+1,in3,0,0))%MOD; ll hs2=(((rv(in1,in2,1,1)*ps2[in2-in1+1])%MOD2)+rv(in2+1,in3,0,1))%MOD2; ans&=blc[i]==make_pair(hs,hs2); } dbg(ans); for(int i=c_r*len;i<=r;i++,j++){ ans&=a[i]==b[j]; } dbg(ans); } return ans; } void solve(){ ps[0]=1; lp(i,1,320) ps[i]=(ps[i-1]*pr)%MOD; ps2[0]=1; lp(i,1,320) ps2[i]=(ps2[i-1]*pr2)%MOD; map<ll,ll>mp; vl tmp; n=II,m=II; lp(i,0,n)a.push_back(II),tmp.push_back(a.back()); lp(i,0,m)b.push_back(II),tmp.push_back(b.back()); sort(r(tmp)); ll v=1; lp(i,0,tmp.size()) if(mp.find(tmp[i])==mp.end()) mp[tmp[i]]=v++; lp(i,0,n)a[i]=mp[a[i]]; lp(i,0,m)b[i]=mp[b[i]]; init(); if(DEBUGGER){ lp(i,0,n)cout<<a[i]<<' ';cout<<endl; lp(i,0,m)cout<<b[i]<<' ';cout<<endl; dbg(len); // lp(i,0,len)cout<<blc[i]<<' ';cout<<endl; lp(i,0,len){ lp(j,0,blcvl[i].size()) cout<<blcvl[i][j]<<' '; cout<<", "; }cout<<endl; // lp(i,0,len)cout<<blc2[i]<<' ';cout<<endl; } ll q=II; while(q--){ if(II==1){ ll i=II-1,x=II; if(mp.find(x)==mp.end()) mp[x]=v++; x=mp[x]; update(i,x); } else{ ll l=II-1,r=II-1; if(query(l,r)) outa("YES"); else outa("NO"); } } } int main(void){ io; int multipletest=0; if(multipletest){ int tc; cin>>tc; while(tc--) solve(); } else solve(); return 0; }