oj.uz

Submission #768547

# Submission time Handle Problem Language Result Execution time Memory
768547 2023-06-28T09:01:46 Z amirhoseinfar1385 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 257 ms 70212 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 55108 KB Output is correct
2 Correct 111 ms 57932 KB Output is correct
3 Correct 113 ms 58092 KB Output is correct
4 Correct 127 ms 58616 KB Output is correct
5 Correct 121 ms 58444 KB Output is correct
6 Correct 127 ms 58880 KB Output is correct
7 Correct 121 ms 59920 KB Output is correct
8 Correct 136 ms 59024 KB Output is correct
9 Correct 128 ms 58820 KB Output is correct
10 Correct 103 ms 57028 KB Output is correct
11 Correct 97 ms 70212 KB Output is correct
12 Correct 88 ms 62832 KB Output is correct
13 Correct 93 ms 66908 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 55108 KB Output is correct
2 Correct 111 ms 57932 KB Output is correct
3 Correct 113 ms 58092 KB Output is correct
4 Correct 127 ms 58616 KB Output is correct
5 Correct 121 ms 58444 KB Output is correct
6 Correct 127 ms 58880 KB Output is correct
7 Correct 121 ms 59920 KB Output is correct
8 Correct 136 ms 59024 KB Output is correct
9 Correct 128 ms 58820 KB Output is correct
10 Correct 103 ms 57028 KB Output is correct
11 Correct 97 ms 70212 KB Output is correct
12 Correct 88 ms 62832 KB Output is correct
13 Correct 93 ms 66908 KB Output is correct
14 Incorrect 257 ms 60556 KB Output isn't correct
15 Halted 0 ms 0 KB -