Submission #468959

#TimeUsernameProblemLanguageResultExecution timeMemory
468959sinamhdvDabbeh (INOI20_dabbeh)C++11
0 / 100
2086 ms161908 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int mod = 1000000363; const int INF = 1e9 + 100; const ll LINF = 1e18 + 100; const int prm = 727; #ifdef DEBUG #define dbg(x) cout << #x << " = " << (x) << endl << flush; #define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; } #else #define dbg(x) ; #define dbgr(s, f) ; #endif #define fast_io ios::sync_with_stdio(0); cin.tie(0); #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define all(x) (x).begin(), (x).end() #define pb push_back #define fr first #define sc second #define endl '\n' const int MAXN = 10100; const int MAXL = 300100; const int MAXT = 500100; int n, q; string t[MAXN]; string s; int lcp[MAXL]; int qans[MAXL]; set<int> hst; int pw[MAXT]; int hsh[MAXL]; vector<pii> qr[MAXL]; int seg[4 * MAXL]; vector<int> vec[MAXL]; int ssz; inline int gethash(int l, int r) { return (mod + (hsh[r + 1] - hsh[l] * (ll)pw[r - l + 1]) % mod) % mod; } inline int getlcp(int i) { int l = 0, r = (int)s.size() - i + 1; while (r - l > 1) { int mid = (r + l) / 2; if (hst.count(gethash(i, i + mid - 1))) l = mid; else r = mid; } return l; } void setind(int i, int x, int v = 1, int l = 0, int r = ssz - 1) { if (l == r) { seg[v] = x; return; } int mid = (r + l) / 2; if (i <= mid) setind(i, x, 2* v, l, mid ); else setind(i, x, 2 *v + 1, mid + 1, r); seg[v] = min(seg[2 * v], seg[2 * v + 1]); } int get(int L, int R, int v = 1, int l = 0, int r = ssz -1) { if (l > R || r < L) return INF; if (l >= L && r <= R) return seg[v]; int mid = (r + l) / 2; return min(get(L, R, 2 * v , l, mid), get(L, R, 2 * v + 1, mid + 1, r)); } int32_t main(void) { fast_io; pw[0] = 1; FOR(i, 1, MAXT) pw[i] = (ll)pw[i - 1] * prm % mod; cin >> n >> q; FOR(i, 0, n) { cin >> t[i]; // prehash ll h = 0; for (char c : t[i]) { h = (prm * h + c) % mod; hst.insert(h); } } cin >> s; ssz = s.size(); // prehash FOR(i, 1, (int)s.size() + 1) hsh[i] = (hsh[i - 1] * (ll)prm + s[i - 1]) % mod; FOR(i, 0, (int)s.size()) lcp[i] = getlcp(i); dbgr(lcp, lcp + (int)s.size()); FOR(i, 0, (int)s.size()) if (lcp[i]) { vec[i + lcp[i] - 1].pb(i); } FOR(i, 0, q) { int l, r; cin >> l >> r; r--; qr[r].pb({l, i}); } fill(seg, seg + 4 * MAXL, INF); for (int r = (int)s.size() - 1; r >= 0; r--) { dbg(r); for (int u : vec[r]) { dbg(u); dbg(seg[1]); setind(u, u); } for (pii p : qr[r]) { dbg(p.fr); int nxt = get(p.fr, ssz - 1); dbg(p.sc); dbg(nxt); if (nxt > r) { qans[p.sc] = -1; continue; } qans[p.sc]++; if (nxt > p.fr) qr[nxt - 1].pb(p); } dbg("=================\n"); } FOR(i, 0, q) cout << qans[i] << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...