oj.uz

Submission #768535

# Submission time Handle Problem Language Result Execution time Memory
768535 2023-06-28T08:52:07 Z amirhoseinfar1385 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 88432 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";*/
		maxa[i]=i-1;
		for(int j=0;j<n;j++){
			int ted=0;
			for(int h=0;h<(int)alls[j].size();h++){
				if(alls[j][h]==s[h+i]){
					ted++;
					continue;
				}
				break;
			}
			maxa[i]=max(maxa[i],i+ted-1);
		}
	}
	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 43 ms 70732 KB Output is correct
2 Correct 125 ms 74012 KB Output is correct
3 Correct 123 ms 75736 KB Output is correct
4 Correct 137 ms 76620 KB Output is correct
5 Correct 128 ms 76452 KB Output is correct
6 Correct 146 ms 77276 KB Output is correct
7 Correct 134 ms 78116 KB Output is correct
8 Correct 151 ms 77292 KB Output is correct
9 Correct 133 ms 76988 KB Output is correct
10 Correct 116 ms 74648 KB Output is correct
11 Correct 104 ms 88432 KB Output is correct
12 Correct 94 ms 80532 KB Output is correct
13 Correct 101 ms 84848 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 35312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 70732 KB Output is correct
2 Correct 125 ms 74012 KB Output is correct
3 Correct 123 ms 75736 KB Output is correct
4 Correct 137 ms 76620 KB Output is correct
5 Correct 128 ms 76452 KB Output is correct
6 Correct 146 ms 77276 KB Output is correct
7 Correct 134 ms 78116 KB Output is correct
8 Correct 151 ms 77292 KB Output is correct
9 Correct 133 ms 76988 KB Output is correct
10 Correct 116 ms 74648 KB Output is correct
11 Correct 104 ms 88432 KB Output is correct
12 Correct 94 ms 80532 KB Output is correct
13 Correct 101 ms 84848 KB Output is correct
14 Execution timed out 2080 ms 35312 KB Time limit exceeded
15 Halted 0 ms 0 KB -