#include <bits/stdc++.h>
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.pb('$');
int n = sz(s);
vector<int> p(n), rnk(n), tmp(n), pn(n), cnt(n);
iota(all(p), 0);
sort(all(p), [&](int i, int j){return s[i] < s[j];});
rep(i,1,n){
rnk[p[i]] = rnk[p[i-1]] + (s[p[i]] != s[p[i-1]]);
}
auto get = [&](int i, int k){
int en = i + (1<<k);
if(en >= n) en -= n;
return pp(rnk[i], rnk[en]);
};
for(int k = 0; (1 << k) < n; k++){
rep(i,0,n) {
pn[i] = p[i] - (1<<k) + n;
if(pn[i] >= n){
pn[i] -= n;
if(pn[i] >= n) pn[i] -= n;
}
}
fill(all(cnt), 0);
rep(i,0,n) cnt[rnk[i]]++;
rep(i,1,n) cnt[i] += cnt[i-1];
per(i,n-1,0) p[--cnt[rnk[pn[i]]]] = pn[i];
tmp[p[0]] = 0;
rep(i,1,n) tmp[p[i]] = tmp[p[i-1]] + (get(p[i], k) != get(p[i-1], k));
rnk.swap(tmp);
}
p.erase(begin(p));
return p;
}
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 + 1, 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 time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
75 ms |
2048 KB |
Output is correct |
| 3 |
Correct |
76 ms |
1984 KB |
Output is correct |
| 4 |
Incorrect |
78 ms |
2788 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
448 ms |
107508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
75 ms |
2048 KB |
Output is correct |
| 3 |
Correct |
76 ms |
1984 KB |
Output is correct |
| 4 |
Incorrect |
78 ms |
2788 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
