#include <bits/stdc++.h>
#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,a[MAX],b[MAX],d[MAX],e[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;
int pow1[MAX],pow2[MAX];
int cost[501][501],can[501][501];
int get_hash_1(int l,int r){
int 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){
int 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));
struct segtree{
int size;
vector<ll> maximum;
void build(vector<int> &a,int x,int lx,int rx){
if(rx-lx==1){
if(lx<(int)a.size()){
maximum[x]=a[lx];
}
return;
}
int m=(lx+rx)/2;
build(a,2*x+1,lx,m);
build(a,2*x+2,m,rx);
maximum[x]=max(maximum[2*x+1],maximum[2*x+2]);
}
void build(vector<int> &a){
build(a,0,0,size);
}
void init(int n){
size=1;
while(size<n){
size*=2;
}
maximum.assign(2*size,-INF);
}
ll get_min(int l,int r,int x,int lx,int rx){
if(lx>=r || rx<=l){
return -INF;
}
if(lx>=l && rx<=r){
return maximum[x];
}
ll s1,s2;
int m=(lx+rx)/2;
s1=get_min(l,r,2*x+1,lx,m);
s2=get_min(l,r,2*x+2,m,rx);
return max(s1,s2);
}
ll get_min(int l,int r){
return get_min(l,r,0,0,size);
}
void set(int i,int v,int x,int lx,int rx){
if(rx-lx==1){
maximum[x]=v;
return;
}
int m=(lx+rx)/2;
if(i<m){
set(i,v,2*x+1,lx,m);
}
else{
set(i,v,2*x+2,m,rx);
}
maximum[x]=max(maximum[2*x+1],maximum[2*x+2]);
}
void set(int i,int v){
set(i,v,0,0,size);
}
};
segtree st[20];
void solve(){
cin >> n >> q;
int p1,p2;
p1=p2=1;
pow1[0]=pow2[0]=1;
for(int i=1;i<=N;i++){
p1=p1*B1;
p2=p2*B2;
p1%=M1;
p2%=M2;
pow1[i]=p1;
pow2[i]=p2;
}
map<array<int,3>,ll> c;
for(int i=0;i<n;i++){
cin >> s[i];
k=(int)s[i].size();
int 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[{h1,h2,j+1}]++;
}
}
cin >> s1;
m=(int)s1.size();
int 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;
if(c[{get_hash_1(j,mid),get_hash_2(j,mid),mid-j+1}]){
l=mid;
}
else{
r=mid-1;
}
}
if(c[{get_hash_1(j,l),get_hash_2(j,l),l-j+1}]){
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_min(j,min(m,sp[i-1][j]+2));
}
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]<y){
res+=(1<<j);
x=sp[j][x];
ok=true;
}
}
else{
int h1=st[j].get_min(x1,min(m,x+2));
//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++;
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
49 ms |
117804 KB |
Output is correct |
| 2 |
Correct |
319 ms |
150692 KB |
Output is correct |
| 3 |
Correct |
295 ms |
142780 KB |
Output is correct |
| 4 |
Correct |
375 ms |
150648 KB |
Output is correct |
| 5 |
Correct |
358 ms |
147960 KB |
Output is correct |
| 6 |
Correct |
405 ms |
155620 KB |
Output is correct |
| 7 |
Correct |
465 ms |
159456 KB |
Output is correct |
| 8 |
Correct |
453 ms |
157704 KB |
Output is correct |
| 9 |
Correct |
371 ms |
153832 KB |
Output is correct |
| 10 |
Correct |
179 ms |
128804 KB |
Output is correct |
| 11 |
Correct |
273 ms |
155684 KB |
Output is correct |
| 12 |
Correct |
186 ms |
137256 KB |
Output is correct |
| 13 |
Correct |
229 ms |
147236 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2045 ms |
299300 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
49 ms |
117804 KB |
Output is correct |
| 2 |
Correct |
319 ms |
150692 KB |
Output is correct |
| 3 |
Correct |
295 ms |
142780 KB |
Output is correct |
| 4 |
Correct |
375 ms |
150648 KB |
Output is correct |
| 5 |
Correct |
358 ms |
147960 KB |
Output is correct |
| 6 |
Correct |
405 ms |
155620 KB |
Output is correct |
| 7 |
Correct |
465 ms |
159456 KB |
Output is correct |
| 8 |
Correct |
453 ms |
157704 KB |
Output is correct |
| 9 |
Correct |
371 ms |
153832 KB |
Output is correct |
| 10 |
Correct |
179 ms |
128804 KB |
Output is correct |
| 11 |
Correct |
273 ms |
155684 KB |
Output is correct |
| 12 |
Correct |
186 ms |
137256 KB |
Output is correct |
| 13 |
Correct |
229 ms |
147236 KB |
Output is correct |
| 14 |
Execution timed out |
2045 ms |
299300 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
