Submission #992010

#TimeUsernameProblemLanguageResultExecution timeMemory
992010sadddDabbeh (INOI20_dabbeh)C++17
0 / 100
298 ms55248 KiB
#include<bits/stdc++.h> #include<fstream> using namespace std; //#pragma GCC optimize("O3") #define sz(a) (int)a.size() #define ALL(v) v.begin(), v.end() #define ALLR(v) v.rbegin(), v.rend() #define ll long long #define pb push_back #define forr(i, a, b) for(int i = a; i < b; i++) #define dorr(i, a, b) for(int i = a; i >= b; i--) #define ld long double #define vt vector #include<fstream> #define fi first #define se second #define pll pair<ll, ll> #define pii pair<int, int> #define mpp make_pair const ld PI = 3.14159265359, prec = 1e-9;; //using u128 = __uint128_t; //const int x[4] = {1, 0, -1, 0}; //const int y[4] = {0, -1, 0, 1}; ll mod = 998244353, pr = 69; const int mxn = 3e5 + 5, mxq = 1e5 + 5, sq = 1005, mxv = 5e4 + 1, lg = 60; //const int base = (1 <<18); const ll inf = 2e9 + 5, neg = -69420, inf2 = 1e14; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll rr(ll l, ll r){ return(uniform_int_distribution<ll>(l, r)(rng)); } // have fun! struct Hash{ vt<ll>hsh, pw; void init(string s){ pw.resize(sz(s) + 1, 0); hsh.resize(sz(s) + 1, 0); for(int i = 0; i < sz(s); i++){ hsh[i + 1] = (hsh[i] * pr + (s[i] - 'a' + 1)) % mod; } pw[0] = 1; for(int i = 1; i <= sz(s); i++){ pw[i] = (pw[i - 1] * pr) % mod; } } ll get(int l, int r){ return((hsh[r + 1] - hsh[l] * pw[r - l + 1] + mod * mod) % mod); } }; Hash ht[mxn + 1], hs; int n, m; string t[mxn + 1], s; pii get(int ids, int idt){ int l = 1, r = min(sz(s) - ids, sz(t[idt])), ans = 0; while(l <= r){ int mid = (l + r) >> 1; if(hs.get(ids, ids + mid - 1) == ht[idt].hsh[mid]){ ans = mid; l = mid + 1; }else{ r = mid - 1; } } if(ans == min(sz(s) - ids, sz(t[idt]))){ return(mpp(ans, sz(s) - ids < sz(t[idt]))); }else{ return(mpp(ans, s[ids + ans] < t[idt][ans])); } } int up[mxn + 1][19]; void solve(){ cin >> n >> m; mod = rr(1e8, 1e9); for(int i = 1; i <= n; i++){ cin >> t[i]; } sort(t + 1, t + n + 1); for(int i = 1; i <= n; i++)ht[i].init(t[i]); cin >> s; hs.init(s); for(int i = 0; i < sz(s); i++){ int l = 1, r = n, ans = 0; while(l <= r){ int mid = (l + r) >> 1; pii cand = get(i, mid); ans = max(ans, cand.fi); if(cand.se == 0){ l = mid + 1; }else{ r = mid - 1; } } up[i][0] = i + ans; } up[sz(s)][0] = sz(s); for(int i = 1; i < 19; i++){ deque<int>dq; for(int j = sz(s); j >= 0; j--){ while(sz(dq) && up[j][i - 1] >= up[dq.back()][i - 1])dq.pop_back(); dq.pb(j); int l = 0, r = sz(dq) - 1, ans; while(l <= r){ int mid = (l + r) >> 1; if(dq[mid] <= up[j][i - 1]){ ans = mid; r = mid - 1; }else{ l = mid + 1; } } up[j][i] = up[dq[ans]][i - 1]; } } while(m--){ int l, r; cin >> l >> r; r--; int ans = 0; for(int i = 18; i >= 0; i--){ if(up[l][i] <= r){ ans += (1 << i); l = up[l][i]; } } cout << ((ans == ((1 << 19) - 1)) ? -1 : ans + 1) << "\n"; } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("TESTROOMS.inp", "r", stdin); //freopen("TESTROOMS.out", "w", stdout); int tt; tt = 1; while(tt--){ solve(); } return(0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...