#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
/*#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")*/
/*#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")*/
using namespace std;
using ll=long long int;
using ld=long double;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define lc v<<1
#define rc v<<1|1
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N=8e5+10,LN=20,M=5e5+10,SQ=350,B=737,inf=1e9+10;
const ll INF=1e18;
const ld ep=1e-7;
const int MH=1000696969,MD=998244353,MOD=1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
ll ans=1;
while (y != 0) {
if (y & 1) ans = ans * x % mod;
y >>= 1;
x = x * x % mod;
}
return ans;
}
int n,t,q,dp[300001][LN][LN],rnk[20][N],P[N],st[N],f,lg[N],ts[N];
string s[10001],S;
pii pr[N];
vector<pii> vec;
vector<int> cnt[N];
void bldSA(){
for (int i=1; i<=t; i++){
rnk[0][i]=S[i-1];
cnt[rnk[0][i]].pb(i);
}
ts[0]=1;
for(int i=0; i<300; i++){
for(int j : cnt[i]){
P[ts[0]++]=j;
}
cnt[i]={};
}
for (int pw=1; pw<LN; pw++) {
for (int i=1; i<=t; i++){
pr[i]={rnk[pw-1][i],i+(1<<(pw-1))>t?0:rnk[pw-1][i+(1<<(pw-1))]};
}
int mx=0;
for(int i=t; i; i--){
ts[rnk[pw-1][P[i]]]=i;
cnt[pr[P[i]].S].pb(P[i]);
mx=max(mx,pr[P[i]].S);
}
for(int i=0; i<=mx; i++){
for(int j : cnt[i]){
P[ts[rnk[pw-1][j]]++]=j;
}
cnt[i]={};
}
rnk[pw][P[1]]=1;
for (int i=2; i<=t; i++){
rnk[pw][P[i]]=rnk[pw][P[i-1]]+(pr[P[i]]!=pr[P[i-1]]);
}
}
}
int LCP(int x, int y){
int ans=0;
for(int i=LN; i--;){
if(rnk[i][x]==rnk[i][y] && max(x,y)<=t){
x+=(1<<i);
y+=(1<<i);
ans|=(1<<i);
}
}
return ans;
}
int get(int c, int l, int r){
int x=lg[r-l+1];
return max(dp[l][c][x],dp[r-(1<<x)+1][c][x]);
}
int main(){
fast_io;
for(int i=0; i<LN; i++){
for(int j=(1<<i); j<(1<<(i+1)); j++) lg[j]=i;
}
cin >> n >> q;
for(int i=1; i<=n; i++) cin >> s[i];
cin >> S;
f=S.size();
for(int i=1; i<=n; i++){
st[i]=S.size()+2;
S+=' '+s[i];
}
t=S.size();
bldSA();
for(int i=1; i<=n; i++){
vec.emplace_back(rnk[LN-1][st[i]],i);
}
sort(vec.begin(),vec.end());
for(int i=1; i<=f; i++){
dp[i][0][0]=i;
int k=rnk[LN-1][i];
auto it=lower_bound(vec.begin(),vec.end(),mp(k,0));
if(it!=vec.end()){
int c=it->S;
dp[i][0][0]=max(dp[i][0][0],LCP(i,st[c])+i);
}
if(it!=vec.begin()){
it--;
int c=it->S;
dp[i][0][0]=max(dp[i][0][0],LCP(i,st[c])+i);
}
dp[i][0][0]=min(dp[i][0][0],f+1);
}
for(int j=1; j<LN; j++){
for(int i=1; i<=f; i++){
if(i+(1<<(j-1))<=f) dp[i][0][j]=max(dp[i][0][j-1],dp[i+(1<<(j-1))][0][j-1]);
else dp[i][0][j]=dp[i][0][j-1];
}
}
for(int pw=1; pw<LN; pw++){
for(int i=1; i<=f; i++){
dp[i][pw][0]=get(pw-1,i,dp[i][pw-1][0]);
}
for(int j=1; j<LN; j++){
for(int i=1; i<=f; i++){
if(i+(1<<(j-1))<=f) dp[i][pw][j]=max(dp[i][pw][j-1],dp[i+(1<<(j-1))][pw][j-1]);
else dp[i][pw][j]=dp[i][pw][j-1];
}
}
}
while(q--){
int l,r,ans=0,x;
cin >> l >> r;
l++;
r++;
x=l;
for(int i=LN; i--;){
int p=get(i,l,x);
if(p<r){
ans|=(1<<i);
x=p;
}
}
if(get(0,l,x)>=r) cout << ans+1 << '\n';
else cout << -1 << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
23628 KB |
Output is correct |
| 2 |
Execution timed out |
2080 ms |
70716 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2072 ms |
74612 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
23628 KB |
Output is correct |
| 2 |
Execution timed out |
2080 ms |
70716 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
