oj.uz

Submission #768540

# Submission time Handle Problem Language Result Execution time Memory
768540 2023-06-28T08:55:01 Z amirhoseinfar1385 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 260 ms 69728 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10;
vector<int>allv[maxn];
int mp[maxn],base=31,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();
	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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 55124 KB Output is correct
2 Correct 123 ms 58048 KB Output is correct
3 Correct 110 ms 57584 KB Output is correct
4 Correct 116 ms 57932 KB Output is correct
5 Correct 114 ms 57980 KB Output is correct
6 Correct 122 ms 58308 KB Output is correct
7 Correct 113 ms 59384 KB Output is correct
8 Correct 118 ms 58436 KB Output is correct
9 Correct 115 ms 58340 KB Output is correct
10 Correct 103 ms 56584 KB Output is correct
11 Correct 91 ms 69728 KB Output is correct
12 Correct 82 ms 62296 KB Output is correct
13 Correct 94 ms 66324 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 55124 KB Output is correct
2 Correct 123 ms 58048 KB Output is correct
3 Correct 110 ms 57584 KB Output is correct
4 Correct 116 ms 57932 KB Output is correct
5 Correct 114 ms 57980 KB Output is correct
6 Correct 122 ms 58308 KB Output is correct
7 Correct 113 ms 59384 KB Output is correct
8 Correct 118 ms 58436 KB Output is correct
9 Correct 115 ms 58340 KB Output is correct
10 Correct 103 ms 56584 KB Output is correct
11 Correct 91 ms 69728 KB Output is correct
12 Correct 82 ms 62296 KB Output is correct
13 Correct 94 ms 66324 KB Output is correct
14 Incorrect 260 ms 60640 KB Output isn't correct
15 Halted 0 ms 0 KB -