Submission #768644

#	Time	Username	Problem	Language	Result	Execution time	Memory
768644		amirhoseinfar1385	Dabbeh (INOI20_dabbeh)	C++17	100 / 100	928 ms	132552 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long long maxn=500000+10;
vector<pair<long long ,long long>>allv[maxn];
long long mp[maxn],base=131,mod=2000000357,ps[maxn],maxa[maxn],sz,rev[maxn];
long long m,n;
string s;
long long lca[20][maxn];
long long mod2=1e9+7,mp2[maxn],rev2[maxn],ps2[maxn];

long long mypow2(long long m,long long y){
	if(y==0){
		return 1;
	}
	long long p=mypow2(m,(y>>1));
	p*=p;
	p%=mod2;
	if(y&1){
		p*=m;
		p%=mod2;
	}
	return p;
}

long long mypow(long long m,long long y){
	if(y==0){
		return 1;
	}
	long long p=mypow(m,(y>>1));
	p*=p;
	p%=mod;
	if(y&1){
		p*=m;
		p%=mod;
	}
	return p;
}

void aval(){
	mp[0]=1;
	for(long long i=1;i<maxn;i++){
		mp[i]=1ll*mp[i-1]*base%mod;
	}
	rev[maxn-1]=mypow(mp[maxn-1],mod-2);
	for(long long i=maxn-2;i>=0;i--){
		rev[i]=1ll*rev[i+1]*base%mod;
	}


	mp2[0]=1;
	for(long long i=1;i<maxn;i++){
		mp2[i]=1ll*mp2[i-1]*base%mod2;
	}
	rev2[maxn-1]=mypow2(mp2[maxn-1],mod2-2);
	for(long long i=maxn-2;i>=0;i--){
		rev2[i]=1ll*rev2[i+1]*base%mod2;
	}
}

long long ww2(long long a){
	if(a>=mod2){
		a-=mod2;
	}
	return a;
}

long long ww(long long a){
	if(a>=mod){
		a-=mod;
	}
	return a;
}

long long pors2(long long l,long long r){
	r++;
	l++;
	long long ret=ps2[r]-ps2[l-1]+mod2;
	ret=ww2(ret);
	ret=1ll*ret*rev2[l-1]%mod2;
	return ret;
}

long long pors(long long l,long long r){
	r++;
	l++;
	long long ret=ps[r]-ps[l-1]+mod;
	ret=ww(ret);
	ret=1ll*ret*rev[l-1]%mod;
	return ret;
}

long long exi(long long lev,pair<long long,long long>w){
	long long p=lower_bound(allv[lev].begin(),allv[lev].end(),w)-allv[lev].begin();
	if(p==(long long)allv[lev].size()||allv[lev][p]!=w){
		return 0;
	}
	return 1;
}

void callca(){
	for(long long j=1;j<maxn;j++){
		if(lca[0][j]==0){
			lca[0][j]=-1;
		}
	}
	for(long long i=1;i<20;i++){
		for(long long j=0;j<maxn;j++){
			if(lca[i-1][j]==-1){
				lca[i][j]=-1;
				continue;
			}
			lca[i][j]=lca[i-1][lca[i-1][j]];
		}
	}
}

void solve(long long l,long long r){
	r--;
	long long res=1;
	if(maxa[l]>=r){
		cout<<1<<"\n";
		return ;
	}
	for(long long i=19;i>=0;i--){
		if(lca[i][l]==-1||maxa[lca[i][l]]<lca[i][l]){
			continue;
		}
		if(maxa[lca[i][l]]>=r){
			continue;
		}
		res+=(1<<i);
	//	cout<<"ha: "<<l<<" "<<i<<" "<<lca[i][l]<<"\n";
		l=lca[i][l];
	}
	res++;
	l=lca[0][l];
	//cout<<l<<" "<<maxa[l]<<" "<<res<<"\n";
	if(l==-1||maxa[l]<r){
		cout<<-1<<"\n";
		return ;
	}
	cout<<res<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	aval();
	//freopen("inp.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	cin>>n>>m;
	for(long long i=0;i<n;i++){
		cin>>s;
		long long unnow=0,unnow2=0;
		for(long long j=0;j<(long long)s.size();j++){
			unnow+=1ll*s[j]*mp[j]%mod;
			unnow=ww(unnow);
			unnow2+=1ll*s[j]*mp2[j]%mod2;
			unnow2=ww2(unnow2);
			allv[j+1].push_back(make_pair(unnow,unnow2));
		}
	}
	for(long long i=0;i<maxn;i++){
		sort(allv[i].begin(),allv[i].end());
		allv[i].resize(unique(allv[i].begin(),allv[i].end())-allv[i].begin());
	}
	cin>>s;
	long long unnow=0,unnow2=0;
	sz=(long long)s.size();
	for(long long j=0;j<(long long)s.size();j++){
		unnow+=1ll*s[j]*mp[j]%mod;
		unnow=ww(unnow);
		unnow2+=1ll*s[j]*mp2[j]%mod2;
		unnow2=ww2(unnow2);
		ps[j+1]=unnow;
		ps2[j+1]=unnow2;
	}
	for(long long i=0;i<sz;i++){	
		long long low=i-1,high=sz,mid;
		while(high-low>1){
			mid=(high+low)>>1;
			if(exi(mid-i+1,make_pair(pors(i,mid),pors2(i,mid)))){
				low=mid;
			}
			else{
				high=mid;
			}
		}
		maxa[i]=low;
		//<<i<<" dsa "<<maxa[i]<<"\n";
	}
	deque<pair<long long,long long>>v;
	v.push_back(make_pair(sz,sz+2));
	for(long long i=sz-1;i>=0;i--){
		long long p=lower_bound(v.begin(),v.end(),make_pair(maxa[i]+2,-1ll))-v.begin();
		p--;
		if(p<0){
			v.push_front(make_pair(i,maxa[i]));
			lca[0][i]=-1;
			continue;
		}
		lca[0][i]=v[p].first;
		while((long long)v.size()>0&&v.front().second<=maxa[i]){
			v.pop_front();
		}
		v.push_front(make_pair(i,maxa[i]));
	}
	callca();
	for(long long i=0;i<m;i++){
		long long l,r;
		cin>>l>>r;
		solve(l,r);
	}
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 50 / 50