Submission #773862

#TimeUsernameProblemLanguageResultExecution timeMemory
773862parsadox2Dabbeh (INOI20_dabbeh)C++14
100 / 100
1452 ms68040 KiB
#include <bits/stdc++.h> #define pb push_back #define F first #define S second #define debug(x) cout << #x << "= " << x << ", " #define ll long long #define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) #define SZ(x) (int) x.size() #define wall cout << endl; using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxn = 3e5 + 10 , Base = 727 , maxl = 20; int n , L , m , pw[2][maxn] , mod[2] , prehsh[2][maxn] , rr[maxn]; pair<int , int> ar[maxn] , adj[maxl][maxn]; int modit(int ty , int a) { if(a >= mod[ty]) return a - mod[ty]; return a; } pair<int , int> get(int l , int r) { int res[2]; if(l == 0) return make_pair(prehsh[0][r] , prehsh[1][r]); for(int ty = 0 ; ty < 2 ; ty++) { res[ty] = 1LL * prehsh[ty][l - 1] * pw[ty][r - l + 1] % mod[ty]; res[ty] = modit(ty , prehsh[ty][r] + mod[ty] - res[ty]); } return make_pair(res[0] , res[1]); } int solve(int l , int r) { if(adj[maxl - 1][l].S < r) return -1; int res = 0; for(int i = maxl - 2 ; i > -1 ; i--) if(adj[i][l].S < r) { res |= (1 << i); l = adj[i][l].F; } res++; return res; } int32_t main() { fast; mod[0] = 1e9 + 7; mod[1] = 998244353; pw[0][0] = pw[1][0] = 1; for(int i = 1 ; i < maxn ; i++) for(int ty = 0 ; ty < 2 ; ty++) pw[ty][i] = 1LL * pw[ty][i - 1] * Base % mod[ty]; cin >> n >> m; vector <pair<int , int>> vec; for(int i = 0 ; i < n ; i++) { string t; cin >> t; int hsh[2]; hsh[0] = hsh[1] = 0; for(int j = 0 ; j < SZ(t) ; j++) { for(int ty = 0 ; ty < 2 ; ty++) { hsh[ty] = 1LL * hsh[ty] * Base % mod[ty]; hsh[ty] = modit(ty , hsh[ty] + t[j]); } vec.pb({hsh[0] , hsh[1]}); } } sort(vec.begin() , vec.end()); vec.resize(unique(vec.begin() , vec.end()) - vec.begin()); string s; cin >> s; L = SZ(s); for(int i = 0 ; i < m ; i++) cin >> ar[i].F >> ar[i].S; prehsh[0][0] = prehsh[1][0] = s[0]; for(int i = 1 ; i < L ; i++) for(int ty = 0 ; ty < 2 ; ty++) { prehsh[ty][i] = 1LL * prehsh[ty][i - 1] * Base % mod[ty]; prehsh[ty][i] = modit(ty , prehsh[ty][i] + s[i]); } for(int i = 0 ; i < L ; i++) { int low = i - 1 , high = L; while(high - low > 1) { int mid = (high + low) >> 1; auto now = get(i , mid); int it = lower_bound(vec.begin() , vec.end() , now) - vec.begin(); if(vec[it] == now) low = mid; else high = mid; } rr[i] = high; } vector <int> st; adj[0][L] = {L , L}; rr[L] = L; st.pb(L); for(int i = L - 1 ; i > -1 ; i--) { if(rr[i] == i) { adj[0][i] = {i , i}; st.pb(i); continue; } int low = -1 , high = SZ(st); while(high - low > 1) { int mid = (high + low) >> 1; if(st[mid] <= rr[i]) high = mid; else low = mid; } adj[0][i] = {st[high] , rr[i]}; while(!st.empty() && rr[i] >= rr[st.back()]) st.pop_back(); st.pb(i); } for(int i = 1 ; i < maxl ; i++) for(int j = 0 ; j <= L ; j++) adj[i][j] = adj[i - 1][adj[i - 1][j].F]; for(int i = 0 ; i < m ; i++) cout << solve(ar[i].F , ar[i].S) << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...