oj.uz

Submission #768537

# Submission time Handle Problem Language Result Execution time Memory
768537 2023-06-28T08:53:32 Z amirhoseinfar1385 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 263 ms 85784 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10;
vector<int>allv[maxn];
int mp[maxn],base=31,mod=1000023469,ps[maxn],maxa[maxn],sz,rev[maxn];
int m,n;
string s;
int lca[20][maxn];
string alls[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();
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>s;
		alls[i]=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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 70652 KB Output is correct
2 Correct 154 ms 73924 KB Output is correct
3 Correct 117 ms 73436 KB Output is correct
4 Correct 145 ms 73988 KB Output is correct
5 Correct 125 ms 73956 KB Output is correct
6 Correct 130 ms 74544 KB Output is correct
7 Correct 147 ms 75524 KB Output is correct
8 Correct 166 ms 74640 KB Output is correct
9 Correct 135 ms 74364 KB Output is correct
10 Correct 108 ms 72328 KB Output is correct
11 Correct 103 ms 85784 KB Output is correct
12 Correct 93 ms 78088 KB Output is correct
13 Correct 95 ms 82336 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 263 ms 76484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 70652 KB Output is correct
2 Correct 154 ms 73924 KB Output is correct
3 Correct 117 ms 73436 KB Output is correct
4 Correct 145 ms 73988 KB Output is correct
5 Correct 125 ms 73956 KB Output is correct
6 Correct 130 ms 74544 KB Output is correct
7 Correct 147 ms 75524 KB Output is correct
8 Correct 166 ms 74640 KB Output is correct
9 Correct 135 ms 74364 KB Output is correct
10 Correct 108 ms 72328 KB Output is correct
11 Correct 103 ms 85784 KB Output is correct
12 Correct 93 ms 78088 KB Output is correct
13 Correct 95 ms 82336 KB Output is correct
14 Incorrect 263 ms 76484 KB Output isn't correct
15 Halted 0 ms 0 KB -