제출 #1260544

#제출 시각아이디문제언어결과실행 시간메모리
1260544mohammad86Dabbeh (INOI20_dabbeh)C++20
100 / 100
633 ms45456 KiB
/* @Date : 2025-08-18 13:18:37 @Author : hasan_86 */ #include <bits/stdc++.h> using namespace std; #define pb push_back #define endl "\n" typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; vector<int> sort_cyclic_shift(string &s) { int n = s.size(); vector<int> p(n), c(n), cnt(max(n, 256)); for (int i = 0; i < n; i++) { cnt[s[i]]++; } for (int i = 1; i < 256; i++) { cnt[i] += cnt[i - 1]; } for (int i = n - 1; i >= 0; i--) { p[--cnt[s[i]]] = i; } int cl = 1; c[p[0]] = 0; for (int i = 1; i < n; i++) { if (s[p[i]] != s[p[i - 1]]) cl++; c[p[i]] = cl - 1; } for (int l = 0; (1 << l) < n; l++) { vector<int> pn(n), cn(n); for (int i = 0; i < n; i++) { pn[i] = p[i] - (1 << l); if (pn[i] < 0) pn[i] += n; } fill(begin(cnt), begin(cnt) + cl, 0); for (int i = 0; i < n; i++) { cnt[c[pn[i]]]++; } for (int i = 1; i < cl; i++) { cnt[i] += cnt[i - 1]; } for (int i = n - 1; i >= 0; i--) { p[--cnt[c[pn[i]]]] = pn[i]; } cl = 1; cn[p[0]] = 0; for (int i = 1; i < n; i++) { pii prv = {c[p[i - 1]], c[(p[i - 1] + (1 << l)) % n]}; pii cur = {c[p[i]], c[(p[i] + (1 << l)) % n]}; if (prv != cur) cl++; cn[p[i]] = cl - 1; } c.swap(cn); } return p; } vector<int> suffix_nxtay(string &S) { S += '#'; vector<int> p = sort_cyclic_shift(S); S.pop_back(); p.erase(p.begin()); return p; } vector<int> cal_lcp(vector<int> &p, string &S) { int n = S.size(); vector<int> rank(n); for (int i = 0; i < n; i++) rank[p[i]] = i; vector<int> lcp(n - 1); int k = 0; for (int i = 0; i < n; i++) { if (rank[i] == n - 1) { k = 0; continue; } int j = p[rank[i] + 1]; while (i + k < n && j + k < n && S[i + k] == S[j + k]) k++; lcp[rank[i]] = k; if (k) k--; } return lcp; } struct node { vector<int> vec; vector<int> cnt; int l, r; }; const int maxN = 10000; const int maxL = 1e6 + 100; string t[maxN]; bool mark[maxL]; int nxt[maxL]; int cnt[maxL]; pii seg[maxL << 2]; void build(int id, int L, int R) { if (L + 1 == R) { seg[id] = pii(nxt[L], L); return; } int mid = (L + R) >> 1; build(id << 1 | 0, L, mid); build(id << 1 | 1, mid, R); seg[id] = max(seg[id << 1], seg[id << 1 | 1]); } pii getmax(int id, int L, int R, int l, int r) { if (L == l && R == r) { return seg[id]; } pii ans = {0, 0}; int mid = (L + R) >> 1; if (l < mid) ans = max(ans, getmax(id << 1 | 0, L, mid, l, min(mid, r))); if (r > mid) ans = max(ans, getmax(id << 1 | 1, mid, R, max(l, mid), r)); return ans; } const int maxlg = 20; int par[maxL][maxlg]; int main () { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> t[i]; } string S; cin >> S; int L = S.size(); for (int i = 0; i < n; i++) { S += '$'; mark[(int)S.size()] = true; S += t[i]; } vector<int> p = suffix_nxtay(S); vector<int> lcp = cal_lcp(p, S); lcp.pb(0); int tmp = 0; for (int i = 0; i < p.size(); i++) { if (mark[p[i]]) { tmp = lcp[i]; } else { nxt[p[i]] = tmp + p[i]; tmp = min(tmp, lcp[i]); } } tmp = 0; for (int i = p.size() - 1; i >= 0; i--) { if (mark[p[i]]) { if (i > 0) tmp = lcp[i-1]; } else { nxt[p[i]] = max(nxt[p[i]], tmp + p[i]); nxt[p[i]] = min(L, nxt[p[i]]); } if (i > 0) tmp = min(tmp, lcp[i-1]); } nxt[L] = L; build(1, 0, L +1); for (int i = 0; i <= L; i++) { int p = getmax(1, 0, L +1, i, min(nxt[i] + 1, L +1)).second; par[i][0] = (p == i ? L + 1 : p); } par[L + 1][0] = L + 1; for (int i = 1; i < maxlg; i++) { for (int j = 0; j <= L + 1; j++) { par[j][i] = par[par[j][i - 1]][i - 1]; } } while (m--) { int l, r; cin >> l >> r; int ans = 0, v = l; for (int i = maxlg - 1; i >= 0; i--) { if (par[v][i] < r) { ans += (1 << i); v = par[v][i]; } } if (nxt[v] < r) { cout << -1 << endl; continue; } if (ans == 0) { cout << 1 << endl; continue; } int d = ans - 1; v = l; for (int i = 0; i < maxlg; i++) { if (d >> i & 1) { v = par[v][i]; } } cout << ans + (nxt[v] < r) << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...