Submission #768547

#	Time	Username	Problem	Language	Result	Execution time	Memory
768547		amirhoseinfar1385	Dabbeh (INOI20_dabbeh)	C++17	25 / 100	257 ms	70212 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10;
vector<int>allv[maxn];
int mp[maxn],base=37,mod=1020023471,ps[maxn],maxa[maxn],sz,rev[maxn];
int m,n;
string s;
int lca[20][maxn];

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(int i=1;i<maxn;i++){
		mp[i]=1ll*mp[i-1]*base%mod;
	}
	rev[maxn-1]=mypow(mp[maxn-1],mod-2);
	for(int i=maxn-2;i>=0;i--){
		rev[i]=1ll*rev[i+1]*base%mod;
	}
}

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

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

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

void callca(){
	for(int j=1;j<maxn;j++){
		if(lca[0][j]==0){
			lca[0][j]=-1;
		}
	}
	for(int i=1;i<20;i++){
		for(int 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(int l,int r){
	r--;
	int res=1;
	if(maxa[l]>=r){
		cout<<1<<"\n";
		return ;
	}
	for(int 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);
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>s;
		int unnow=0;
		for(int j=0;j<(int)s.size();j++){
			unnow+=1ll*(s[j]-'a'+1)*mp[j]%mod;
			unnow=ww(unnow);
			allv[j+1].push_back(unnow);
		}
	}
	for(int 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;
	int unnow=0;
	sz=(int)s.size();
	for(int j=0;j<(int)s.size();j++){
		unnow+=1ll*(s[j]-'a'+1)*mp[j]%mod;
		unnow=ww(unnow);
		ps[j+1]=unnow;
	}
	for(int i=0;i<sz;i++){	
		int low=i-1,high=sz,mid;
		while(high-low>1){
			mid=(high+low)>>1;
			if(exi(mid-i+1,pors(i,mid))){
				low=mid;
			}
			else{
				high=mid;
			}
		}
		maxa[i]=low;
		//<<i<<" dsa "<<maxa[i]<<"\n";
	}
	deque<pair<int,int>>v;
	v.push_back(make_pair(sz,sz+2));
	for(int i=sz-1;i>=0;i--){
		int p=lower_bound(v.begin(),v.end(),make_pair(maxa[i]+2,-1))-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((int)v.size()>0&&v.front().second<=maxa[i]){
			v.pop_front();
		}
		v.push_front(make_pair(i,maxa[i]));
	}
	callca();
	for(int i=0;i<m;i++){
		int l,r;
		cin>>l>>r;
		solve(l,r);
	}
}

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