This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#define int ll
#define MAX 1000001
#define INF INT_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define outputar(a,b){\
for(int i=0;i<b;i++){\
cout << a[i] << " ";\
}\
cout << endl;\
}
#define outputvec(a){\
for(auto x:a){\
cout << (int)x << " ";\
}\
cout << endl;\
}
#define reset(a,n,v){\
for(int i=0;i<n;i++){\
a[i]=v;\
}\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
freopen((filename+".in").c_str(),"r",stdin);
freopen((filename+".out").c_str(),"w",stdout);
}
int n,q,t=1,m,k,x,y,z,x2,y2,z2,d[MAX],e[MAX];
long long a[MAX],b[MAX];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string s[MAX],str[MAX];
//int e[1001][1001];
string s1,s2,s3;
const int mod = 998244353;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int B1=133,B2=135,M1=1e9+7,M2=1e9+9;
long long pow1[MAX],pow2[MAX];
int cost[501][501],can[501][501];
int get_hash_1(int l,int r){
long long h=a[r];
if(l!=0){
h-=a[l-1];
}
if(h<0){
h+=M1;
}
h*=pow1[l];
h%=M1;
return h;
}
int get_hash_2(int l,int r){
long long h=b[r];
if(l!=0){
h-=b[l-1];
}
if(h<0){
h+=M2;
}
h*=pow2[l];
h%=M2;
return h;
}
int N=500000;
vector<vector<int>> sp(20,vector<int>(300001));
int lg[MAX];
struct sp_tb{
vector<vector<int>> sp;
int sz;
void init(int n){
sp.resize(20,vector<int>(n));
sz=n;
}
void build(vector<int> &a){
for(int i=0;i<sz;i++){
sp[0][i]=a[i];
}
for(int j=1;j<20;j++){
for(int i=0;i+(1<<j)-1<sz;i++){
sp[j][i]=max(sp[j-1][i],sp[j-1][i+(1<<(j-1))]);
}
}
}
int get_max(int l,int r){
int i=r-l+1;
i=lg[i];
return max(sp[i][l],sp[i][r-(1<<i)+1]);
}
};
sp_tb st[20];
vector<vector<pll>> c(500001);
void solve(){
cin >> n >> q;
long long p1,p2;
p1=p2=1;
pow1[0]=pow2[0]=1;
lg[0]=-1;
for(int i=1;i<=N;i++){
lg[i]=lg[i/2]+1;
p1=p1*B1;
p2=p2*B2;
p1%=M1;
p2%=M2;
pow1[i]=p1;
pow2[i]=p2;
}
for(int i=0;i<n;i++){
cin >> s[i];
k=(int)s[i].size();
long long h1,h2;
h1=h2=0;
for(int j=0;j<k;j++){
h1+=(s[i][j]*pow1[N-j])%M1;
h1%=M1;
h2+=(s[i][j]*pow2[N-j])%M2;
h2%=M2;
c[j+1].pb({h1,h2});
}
}
for(int i=0;i<=N;i++){
sortv(c[i]);
}
cin >> s1;
m=(int)s1.size();
long long h1,h2;
h1=h2=0;
for(int j=0;j<m;j++){
h1+=(s1[j]*pow1[N-j])%M1;
h1%=M1;
h2+=(s1[j]*pow2[N-j])%M2;
h2%=M2;
a[j]=h1;
b[j]=h2;
}
for(int j=0;j<m;j++){
int l,r;
l=j;
r=m-1;
while(l<r){
int mid=(l+r+1)/2;
pll p={get_hash_1(j,mid),get_hash_2(j,mid)};
auto it=lb(c[mid-j+1],p);
if(it!=c[mid-j+1].end() && (*it)==p){
l=mid;
}
else{
r=mid-1;
}
}
pll p={get_hash_1(j,l),get_hash_2(j,l)};
auto it=lb(c[l-j+1],p);
if(it!=c[l-j+1].end() && *it==p){
d[j]=l;
}
else{
d[j]=-1;
}
sp[0][j]=d[j];
}
st[0].init(m);
st[0].build(sp[0]);
for(int i=1;i<20;i++){
for(int j=0;j<m;j++){
if(sp[i-1][j]==-1){
sp[i][j]=-1;
continue;
}
sp[i][j]=st[i-1].get_max(j,min(m-1,sp[i-1][j]+1));
}
st[i].init(m);
st[i].build(sp[i]);
}
for(int i=0;i<q;i++){
cin >> x >> y;
y--;
int x1=x;
int res=0;
bool ok=false,ok1=false;
if(sp[19][x]<y){
ok1=true;
}
for(int j=19;j>=0;j--){
if(!ok){
//cout << x1 << " " << j << " " << sp[j][x] << "\n";
if(sp[j][x]!=-1 && sp[j][x]<y){
res+=(1<<j);
x=sp[j][x];
ok=true;
}
}
else{
int h1=st[j].get_max(x1,min(m-1,x+1));
//cout << x1 << " zor" << y << " " << h1 << "\n";
if(h1<y){
res+=(1<<j);
x=h1;
}
}
}
if(ok1){
res=-2;
}
cout << res+1 << "\n";
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input13.txt","r",stdin);
//cin >> t;
ll cnt1=1;
while(t--){
solve();
cnt1++;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |