Submission #470233

#TimeUsernameProblemLanguageResultExecution timeMemory
470233AmirrezaMDabbeh (INOI20_dabbeh)C++14
25 / 100
1619 ms459800 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; #define vc vector #define pb push_back const int MAXN = 5e5 + 55 , ss = 1 << 19 , lg = 20; const int p[3] = {233 , 253 , 239} , mod[3] = {1000000007 , 1000000009 , 1000000033}; ll pw(ll a , ll b , int t){ ll ret = 1; while(b){ if(b&1) ret = (ret * a) % mod[t]; a = (a * a) % mod[t]; b >>= 1; } return ret; } int n , q , l; string s; bitset<1000000040> mark[3]; int pp[3][MAXN] , inv[3][MAXN] , hsh[3][MAXN]; int get(int l , int r , int t){ int ret = hsh[t][r]; if(l){ ret -= hsh[t][l-1]; if(ret < 0) ret += mod[t]; } ret = (1ll * ret * inv[t][l]) % mod[t]; return ret; } int lim[MAXN]; int segTree[ss<<1]; int get(int v , int tl , int tr , int l , int r){ if(l > tr or r < tl or r < l) return -1; if(l <= tl and r >= tr) return segTree[v]; int mid = (tl + tr) >> 1; int lf = get(v<<1 , tl , mid , l , r), rt = get((v<<1)^1 , mid+1 , tr , l , r); int ans = lf; if(rt != -1 and (ans == -1 or lim[rt] > lim[ans])) ans = rt; return ans; } void upd(int id){ int pos = id + ss; while(pos){ if(segTree[pos] == -1 or lim[id] > lim[segTree[pos]]) segTree[pos] = id; pos >>= 1; } } int par[MAXN] , up[MAXN][lg][2] , h[MAXN]; vc<int> adj[MAXN]; void dfs(int v){ up[v][0][0] = (par[v] == -1 ? v : par[v]); up[v][0][1] = lim[v]; for(int i = 1 ; i < lg ; i++){ up[v][i][0] = up[up[v][i-1][0]][i-1][0]; up[v][i][1] = max(up[v][i-1][1] , up[up[v][i-1][0]][i-1][1]); } for(int u : adj[v]) h[u] = h[v] + 1 , dfs(u); } int main(){ memset(segTree , -1 , sizeof segTree); for(int t = 0 ; t < 3 ; t++){ pp[t][0] = 1; for(int i = 1 ; i < MAXN ; i++) pp[t][i] = (1ll * pp[t][i-1] * p[t]) % mod[t]; for(int i = 0 ; i < MAXN ; i++) inv[t][i] = pw(pp[t][i] , mod[t]-2 , t); } cin >> n >> q; for(int i = 0 ; i < n ; i++){ cin >> s; int cur[3] = {}; for(int t = 0 ; t < 3 ; t++){ for(int i = 0 ; i < (int)s.size() ; i++){ cur[t] = (cur[t] + 1ll * s[i] * pp[t][i]) % mod[t]; mark[t][cur[t]] = 1; } } } cin >> s; l = s.size(); for(int t = 0 ; t < 3 ; t++){ for(int i = 0 ; i < l ; i++){ if(i) hsh[t][i] = hsh[t][i-1]; hsh[t][i] = (hsh[t][i] + 1ll * s[i] * pp[t][i]) % mod[t]; } } for(int i = 0 ; i < l ; i++){ int lo = 0 , hi = l - i + 1; while(hi - lo > 1){ int m = (hi + lo) >> 1; if(mark[0][get(i,i+m-1,0)] and mark[1][get(i,i+m-1,1)]) lo = m; else hi = m; } lim[i] = i + lo - 1; if(lim[i] >= i) upd(i); } for(int i = 0 ; i < l ; i++){ par[i] = get(1 , 0 , ss-1 , i+1 , lim[i]+1); if(par[i] > -1) adj[par[i]].pb(i); } for(int i = 0 ; i < l ; i++){ if(par[i] == -1) dfs(i); } // for(int i = 0 ; i <= l ; i++){ // cout << i << " " << lim[i] << " " << par[i] << " : " << endl; // for(int j = 0 ; j < lg ; j++) cout << up[i][j][0] << " "; // cout << endl; // for(int j = 0 ; j < lg ; j++) cout << up[i][j][1] << " "; // cout << endl; // } while(q--){ int l , r; cin >> l >> r; r--; int v = l; for(int i = lg-1 ; i >= 0 ; i--){ if(up[v][i][1] < r) v = up[v][i][0]; } if(v != -1 and lim[v] >= r) cout << h[l] - h[v] + 1 << endl; else cout << -1 << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...