Data Structure:
Problem Link: QCHEF
My Solution:
Click to See Code
// // main.cpp // QCHEF // // Created by Matrix.code on 3/14/17. // Copyright © 2017 Matrix.code. All rights reserved. // #include<bits/stdc++.h> using namespace std; /*------- Constants---- */ #define Long long long #define Ulong unsigned long long #define FOR(I,A,B) for(int I = (A); I < (B) ; ++ I) #define REP(i,n) for( int i=0 ; i < n ; i++ ) #define mp make_pair #define pb push_back #define all(x) (x).begin(),(x).end() #define PI acos(-1.0) #define EPS 1e-9 #define F first #define S second #define lc ((n)<<1) #define rc ((n)<<1|1) #define db(x) cout << #x << " -> " << x << endl; #define Di(x) int x;scanf("%d",&x) #define in(x) input(x) #define in2(x,y) input(x), input(y) #define in3(x,y,z) input(x), input(y),input(z) #define ins(x) scanf("%s",x) #define ind(x) scanf("%lf",&x) #define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name)) #define IO ios_base::sync_with_stdio(0);cin.tie(0) #define READ freopen("/Users/matrixcode/Desktop/in.txt","r",stdin) #define WRITE freopen("/Users/matrixcode/Desktop/out.txt","w",stdout) template<class T > void input(T &x){ char c = getchar();x = 0; for(;(c<48 || c>57);c = getchar()); for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;} } inline long long bigmod(long long p,long long e,long long M){ long long ret = 1; for(; e > 0; e >>= 1){ if(e & 1) ret = (ret * p) % M; p = (p * p) % M; } return ret; } template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);} template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);} /***************************** END OF TEMPLATE *******************************/ const int N = 1e5+5; const int RootN = 350; int n,m,q; int a[N]; int Beg[RootN] , End[RootN], Id[N] , dp[RootN][N], dp2[RootN][N]; int block; int main() { in3(n,m,q); REP(i,n) in(a[i]); block = 2*sqrt(n)+1; REP(i,n) { Id[i] = i/block; if(i%block==0){ Beg[i/block] = i; End[i/block] = min(n-1, (Id[i]+1)*block-1); } } for(int i = 0;i <= Id[n-1] ; i++ ) { int Map[N]; ms(Map,-1); int iM = 0; for(int j = Beg[i] ; j < n ;j ++ ) { if(Map[a[j]]>=0) { iM = max(iM, j - Map[a[j]] ); } else Map[a[j]] = j; dp[i][j] = iM; } } for(int i=0;i<=Id[n-1]; i++ ){ int Map[N]; ms(Map,-1); int iM = 0; for(int j= End[i]; j>= 0; j--) { if(Map[a[j]]>=0) { iM = max(iM, Map[a[j]] - j ); } else Map[a[j]] = j; dp2[i][j] = iM; } } int x,y; int Map[N]; ms(Map,-1); while(q--) { in2(x,y); x--,y--; if(Id[x]== Id[y]) { int ans = 0; for(int i= x;i <=y;i++) { if(Map[a[i]]>=0) { ans = max(ans, i - Map[a[i]] ); } else Map[a[i]] = i; } for(int i=x;i<=y;i++){ Map[a[i]] = -1; } printf("%d\n",ans); } else { int L = (x== Beg[Id[x]]) ? Id[x] : Id[x]+1; int R = (y== End[Id[y]]) ? Id[y] : Id[y]-1; int ans = 0; if(Beg[L] <= y) ans = max(ans, dp[L][y]); if(x <= End[R]) ans = max(ans, dp2[R][x]); vector<pair<int,int> > v; for(int i=x;i<Beg[L];i++)v.push_back(mp(a[i],i)); for(int i=End[R]+1;i<=y;i++)v.push_back(mp(a[i],i)); for(auto a: v) { if(Map[a.F] >= 0) { ans = max(ans, a.S - Map[a.F]); }else Map[a.F] = a.S; } for(auto a: v) { Map[a.F] = -1; } printf("%d\n",ans); } } return 0; }
Problem Link: CUBTOWER
My Solution:
Click to See Code
// // main.cpp // CUBTOWER // // Created by Matrix.code on 3/15/17. // Copyright © 2017 Matrix.code. All rights reserved. // #include<bits/stdc++.h> using namespace std; /*------- Constants---- */ #define Long long long #define Ulong unsigned long long #define FOR(I,A,B) for(int I = (A); I < (B) ; ++ I) #define REP(i,n) for( int i=0 ; i < n ; i++ ) #define mp make_pair #define pb push_back #define all(x) (x).begin(),(x).end() #define PI acos(-1.0) #define EPS 1e-9 #define F first #define S second #define lc ((n)<<1) #define rc ((n)<<1|1) #define db(x) cout << #x << " -> " << x << endl; #define Di(x) int x;scanf("%d",&x) #define in(x) input(x) #define in2(x,y) input(x), input(y) #define in3(x,y,z) input(x), input(y),input(z) #define ins(x) scanf("%s",x) #define ind(x) scanf("%lf",&x) #define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name)) #define IO ios_base::sync_with_stdio(0);cin.tie(0) #define READ freopen("/Users/matrixcode/Desktop/in.txt","r",stdin) #define WRITE freopen("/Users/matrixcode/Desktop/out.txt","w",stdout) template<class T > void input(T &x){ char c = getchar();x = 0; for(;(c<48 || c>57);c = getchar()); for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;} } inline long long bigmod(long long p,long long e,long long M){ long long ret = 1; for(; e > 0; e >>= 1){ if(e & 1) ret = (ret * p) % M; p = (p * p) % M; } return ret; } template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);} template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);} /***************************** END OF TEMPLATE *******************************/ const int N = 2e5+5; const int RootN= 350; struct Event{ int type; int l,r; int Time; }; vector<Event> e[N]; int n,m,q; long long BASE = 37 , mod = 1e9+7; long long H(char s[]) { long long h =0; for(int i=0;s[i];i++) { h = (BASE * h + s[i]-'a' + 1 ) % mod; } return h; } long long value[N]; char str[N]; int len[N]; unordered_map<long long,int> Map; vector<long long> NString[N]; int uniqueLen[N]; int TLen; long long POW[N]; void append( int idx, char c) { int v = c-'a' + 1; long long pre = NString[idx].size() ? NString[idx].back() : 0; NString[idx].push_back((v + BASE* pre ) % mod); int ptr = (int) NString[idx].size()-1; for(int i=0;i < TLen ;i ++) { int l = uniqueLen[i]; if(l > ptr + 1) break; long long o = ((NString[idx][ptr] - POW[l] * (ptr - l>=0 ? NString[idx][ptr-l] : 0)) % mod + mod ) % mod; if(Map.count(o) && len[Map[o]] == l ) { e[Map[o]].push_back({0,idx,-1,-1}); } } } int block; int Beg[RootN] ,End[RootN], Sum1[RootN] , Sum2[RootN], id[N]; int Arr1[N] , Arr2[N]; long long Ans[N]; void update(int idx) { Arr1[idx] ++; Sum1[id[idx]] ++; if(Arr2[idx] == 0) Arr2[idx]=1 , Sum2[id[idx]] ++; } long long Q1(int x,int y) { long long ans = 0; if(id[x]==id[y]) { for(int i=x;i<=y;i++) { ans+= Arr1[i]; } return ans; } int L = (x==Beg[id[x]]) ? id[x] : id[x]+1; int R = (x==End[id[y]]) ? id[y] : id[y]-1; for(int i=x;i<Beg[L];i++) ans += Arr1[i]; for(int i=y;i>End[R];i--) ans += Arr1[i]; for(int i=L;i<=R;i++) ans += Sum1[i]; return ans; } long long Q2(int x,int y) { long long ans = 0; if(id[x]==id[y]) { for(int i=x;i<=y;i++) { ans+= Arr2[i]; } return ans; } int L = (x==Beg[id[x]]) ? id[x] : id[x]+1; int R = (x==End[id[y]]) ? id[y] : id[y]-1; for(int i=x;i<Beg[L];i++) ans += Arr2[i]; for(int i=y;i>End[R];i--) ans += Arr2[i]; for(int i=L;i<=R;i++) ans += Sum2[i]; return ans; } void Process(int idx) { for(auto a: e[idx]) { if(a.type == 0) { update(a.l); } else if(a.type == 1) { Ans[a.Time] = Q2(a.l,a.r); } else if(a.type == 2) { Ans[a.Time] = Q1(a.l,a.r); } } for(int i=0;i<RootN;i++) Sum1[i] = Sum2[i] =0; for(auto a: e[idx]) { if(a.type == 0) { Arr1[a.l]=0; Arr2[a.l]=0; } } } int main() { in3(n,m,q); POW[0]=1; for(int i=1;i < N;i ++) { POW[i] = (POW[i-1] * BASE ) % mod; } block = sqrt(n)+1; for(int i=0;i<n;i++){ id[i] = i/block; if(i%block==0){ Beg[id[i]] = i; End[id[i]] = min(n-1, (id[i] + 1) * block - 1) ; } } for(int i=0;i<m;i++){ scanf("%s",str); reverse(str,str+strlen(str)); value[i] = H(str); len[i] = strlen(str); Map[value[i]] = i; uniqueLen[i] = len[i]; } sort(uniqueLen, uniqueLen + m); TLen = unique(uniqueLen, uniqueLen + m) - uniqueLen; int t,l,r,p; char ch; for(int i=0;i<q;i++) { scanf("%d",&t); if(t==0) { scanf("%d %c",&l,&ch); l--; append(l,ch); } else if(t==1) { scanf("%d %d %d",&l,&r,&p); l--,r--,p--; e[p].push_back({1,l,r,i}); } else if(t==2) { scanf("%d %d %d",&l,&r,&p); l--,r--,p--; e[p].push_back({2,l,r,i}); } } ms(Ans,-1); for(int i=0;i<m;i++) { Process(i); } for(int i= 0;i < q;i ++) if(Ans[i] >= 0)printf("%lld\n",Ans[i]); return 0; }
Thanks for sharing….
LikeLike