Submission #634517

#TimeUsernameProblemLanguageResultExecution timeMemory
634517MohammadAghilDabbeh (INOI20_dabbeh)C++17
100 / 100
1029 ms120876 KiB
#include <bits/stdc++.h> //#pragma GCC optimize("Ofast,unroll-loops") //#pragma GCC target ("avx2") using namespace std; typedef long long ll; typedef pair<int, int> pp; #define rep(i,l,r) for(int i = (l); i < (r); i++) #define per(i,r,l) for(int i = (r); i >= (l); i--) #define sz(x) (int)x.size() #define all(x) begin(x), end(x) #define pb push_back #define ff first #define ss second void dbg(){ cerr << endl; } template<typename Head, typename... Tail> void dbg(Head h, Tail... t){ cerr << " " << h << ","; dbg(t...); } #define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">:", dbg(__VA_ARGS__) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void IOS(){ cin.tie(0) -> sync_with_stdio(0); // #ifndef ONLINE_JUDGE // freopen("inp.txt", "r", stdin); // freopen("out.txt", "w", stdout); // #endif } const ll mod = 1e9 + 7, mod2 = 1e9 + 9, maxn = 3e5 + 5, lg = 19, inf = ll(1e9) + 5; /* struct C{ int operator()(pair<int, int> x) const { return x.ff^x.ss; } }; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; gp_hash_table<pair<int, int>, bool, C> is; void add(string s){ pp hsh = {0, 0}; for(char c: s){ hsh.ff = (hsh.ff*p + c - 'a' + 1)%mod; hsh.ss = (hsh.ss*p + c - 'a' + 1)%mod2; is[hsh] = true; } } ll pw1[maxn], pw2[maxn]; pp hsh[maxn]; void build_hash(string s){ rep(i,0,sz(s)){ hsh[i].ff = ((i?hsh[i-1].ff:0)*p + s[i] - 'a' + 1)%mod; hsh[i].ss = ((i?hsh[i-1].ss:0)*p + s[i] - 'a' + 1)%mod2; } pw1[0] = pw2[0] = 1; rep(i,1,sz(s) + 1){ pw1[i] = pw1[i-1]*p%mod; pw2[i] = pw2[i-1]*p%mod2; } } pair<int, int> get_hsh(int l, int r){ return { (hsh[r].ff - (l?hsh[l-1].ff*pw1[r-l+1]%mod:0) + mod)%mod, (hsh[r].ss - (l?hsh[l-1].ss*pw2[r-l+1]%mod2:0) + mod2)%mod2 }; } */ int nxt[maxn][lg], nxt_id[maxn][lg]; pair<int, int> rmq[maxn][lg]; int lgg[maxn], m; void build_rmq(int x){ m++; rep(i,0,m) rmq[i][0] = {nxt[i][x], i}; rep(i,2,m + 1) lgg[i] = lgg[i>>1] + 1; rep(j,1,lg){ rep(i,0,m - (1<<j) + 1){ rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]); } } m--; } pp get_rmq(int l, int r){ int k = lgg[r - l + 1]; return max(rmq[l][k], rmq[r-(1<<k)+1][k]); } vector<int> SuffixArray(string s){ s += '$'; int n = sz(s); vector<int> srt(n); iota(all(srt), 0); sort(all(srt), [&](int i, int j){ return s[i] < s[j]; }); vector<int> rnk(n); rnk[srt[0]] = 0; rep(i,1,n){ rnk[srt[i]] = rnk[srt[i-1]] + (s[srt[i]] != s[srt[i-1]]); } for(int k = 1; k <= n; k <<= 1){ sort(all(srt), [&](int i, int j){ if(rnk[i] == rnk[j]){ return rnk[i+k] < rnk[j+k]; } return rnk[i] < rnk[j]; }); vector<int> tmp(n); tmp[srt[0]] = 0; rep(i,1,n){ tmp[srt[i]] = tmp[srt[i-1]] + (rnk[srt[i]] != rnk[srt[i-1]] || rnk[srt[i]+k] != rnk[srt[i-1]+k]); } rnk = tmp; // rep(i,0,n) er(i, k, rnk[i]); // er(n); } srt.erase(begin(srt)); return srt; } int main(){ IOS(); int n, q; cin >> n >> q; vector<string> t(n); rep(i,0,n){ cin >> t[i]; } string s; cin >> s; m = sz(s); vector<int> srt = SuffixArray(s); // int rr = 0; // for(int c: srt){ // cerr << rr++ << ' ' << string(begin(s) + c, end(s)) << endl; // } vector<vector<pp>> add(m), rem(m + 1); int tmp = 0; rep(i,0,n){ int lx = 0, rx = m, ptr = 0; for(char c: t[i]){ int lx1 = lx-1, rx1 = rx; while(lx1 + 1 < rx1){ int mid = (lx1 + rx1)>>1; int en = srt[mid] + ptr; if(en >= m || c > s[en]) lx1 = mid; else rx1 = mid; } int lx2 = lx1, rx2 = rx; while(lx2 + 1 < rx2){ int mid = (lx2 + rx2)>>1; int en = srt[mid] + ptr; if(en >= m || c >= s[en]) lx2 = mid; else rx2 = mid; } if(lx1 == lx2) break; ptr++; lx = rx1, rx = rx2; add[lx].pb({ptr, tmp}); rem[rx-1].pb({ptr, tmp}); tmp++; // er(i, lx, rx-1); } } rep(j,0,lg) nxt[m][j] = nxt_id[m][j] = m; vector<bool> is(maxn<<1); priority_queue<pp> pq; rep(i,0,m){ for(pp c: add[i]) pq.push(c), is[c.ss] = true; while(sz(pq) && !is[pq.top().ss]) pq.pop(); nxt[srt[i]][0] = srt[i]; if(sz(pq)) nxt[srt[i]][0] += pq.top().ff; for(pp c: rem[i]) is[c.ss] = false; } // rep(i,0,m) er(i, nxt[i][0]); /* build_hash(s); rep(i,0,m){ int lx = i-1, rx = m; while(lx + 1 < rx){ int mid = (lx + rx)>>1; if(is[get_hsh(i, mid)]) lx = mid; else rx = mid; } nxt[i][0] = rx; } */ build_rmq(0); rep(i,0,m){ nxt_id[i][0] = get_rmq(i, nxt[i][0]).ss; } rep(j,1,lg){ rep(i,0,m){ nxt[i][j] = nxt[nxt_id[i][j-1]][j-1], nxt_id[i][j] = nxt_id[nxt_id[i][j-1]][j-1]; } } while(q--){ int l, r; cin >> l >> r; r--; if(nxt[l][lg-1] <= r) cout << -1 << '\n'; else{ int ans = 0; per(i,lg-1,0){ int nx = nxt[l][i]; if(nx <= r){ ans |= 1<<i; l = nxt_id[l][i]; } } cout << ans + 1 << '\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...