oj.uz

Submission #768644

# Submission time Handle Problem Language Result Execution time Memory
768644 2023-06-28T10:28:01 Z amirhoseinfar1385 Dabbeh (INOI20_dabbeh) C++17
100 / 100
 928 ms 132552 KB 
#include<bits/stdc++.h>
using namespace std;
const long long maxn=500000+10;
vector<pair<long long ,long long>>allv[maxn];
long long mp[maxn],base=131,mod=2000000357,ps[maxn],maxa[maxn],sz,rev[maxn];
long long m,n;
string s;
long long lca[20][maxn];
long long mod2=1e9+7,mp2[maxn],rev2[maxn],ps2[maxn];

long long mypow2(long long m,long long y){
	if(y==0){
		return 1;
	}
	long long p=mypow2(m,(y>>1));
	p*=p;
	p%=mod2;
	if(y&1){
		p*=m;
		p%=mod2;
	}
	return p;
}

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


	mp2[0]=1;
	for(long long i=1;i<maxn;i++){
		mp2[i]=1ll*mp2[i-1]*base%mod2;
	}
	rev2[maxn-1]=mypow2(mp2[maxn-1],mod2-2);
	for(long long i=maxn-2;i>=0;i--){
		rev2[i]=1ll*rev2[i+1]*base%mod2;
	}
}

long long ww2(long long a){
	if(a>=mod2){
		a-=mod2;
	}
	return a;
}

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

long long pors2(long long l,long long r){
	r++;
	l++;
	long long ret=ps2[r]-ps2[l-1]+mod2;
	ret=ww2(ret);
	ret=1ll*ret*rev2[l-1]%mod2;
	return ret;
}

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

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

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 105972 KB Output is correct
2 Correct 147 ms 115944 KB Output is correct
3 Correct 142 ms 112480 KB Output is correct
4 Correct 148 ms 114184 KB Output is correct
5 Correct 144 ms 113920 KB Output is correct
6 Correct 153 ms 115316 KB Output is correct
7 Correct 147 ms 118628 KB Output is correct
8 Correct 172 ms 116260 KB Output is correct
9 Correct 145 ms 115356 KB Output is correct
10 Correct 132 ms 108992 KB Output is correct
11 Correct 149 ms 120572 KB Output is correct
12 Correct 116 ms 113112 KB Output is correct
13 Correct 119 ms 117264 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 120724 KB Output is correct
2 Correct 380 ms 123464 KB Output is correct
3 Correct 362 ms 121288 KB Output is correct
4 Correct 330 ms 118924 KB Output is correct
5 Correct 321 ms 118564 KB Output is correct
6 Correct 386 ms 123548 KB Output is correct
7 Correct 397 ms 124200 KB Output is correct
8 Correct 376 ms 122560 KB Output is correct
9 Correct 387 ms 123548 KB Output is correct
10 Correct 393 ms 124428 KB Output is correct
11 Correct 350 ms 121660 KB Output is correct
12 Correct 343 ms 120612 KB Output is correct
13 Correct 401 ms 126196 KB Output is correct
14 Correct 385 ms 124872 KB Output is correct
15 Correct 293 ms 118028 KB Output is correct
16 Correct 181 ms 127100 KB Output is correct
17 Correct 171 ms 120484 KB Output is correct
18 Correct 172 ms 120592 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 105972 KB Output is correct
2 Correct 147 ms 115944 KB Output is correct
3 Correct 142 ms 112480 KB Output is correct
4 Correct 148 ms 114184 KB Output is correct
5 Correct 144 ms 113920 KB Output is correct
6 Correct 153 ms 115316 KB Output is correct
7 Correct 147 ms 118628 KB Output is correct
8 Correct 172 ms 116260 KB Output is correct
9 Correct 145 ms 115356 KB Output is correct
10 Correct 132 ms 108992 KB Output is correct
11 Correct 149 ms 120572 KB Output is correct
12 Correct 116 ms 113112 KB Output is correct
13 Correct 119 ms 117264 KB Output is correct
14 Correct 348 ms 120724 KB Output is correct
15 Correct 380 ms 123464 KB Output is correct
16 Correct 362 ms 121288 KB Output is correct
17 Correct 330 ms 118924 KB Output is correct
18 Correct 321 ms 118564 KB Output is correct
19 Correct 386 ms 123548 KB Output is correct
20 Correct 397 ms 124200 KB Output is correct
21 Correct 376 ms 122560 KB Output is correct
22 Correct 387 ms 123548 KB Output is correct
23 Correct 393 ms 124428 KB Output is correct
24 Correct 350 ms 121660 KB Output is correct
25 Correct 343 ms 120612 KB Output is correct
26 Correct 401 ms 126196 KB Output is correct
27 Correct 385 ms 124872 KB Output is correct
28 Correct 293 ms 118028 KB Output is correct
29 Correct 181 ms 127100 KB Output is correct
30 Correct 171 ms 120484 KB Output is correct
31 Correct 172 ms 120592 KB Output is correct
32 Correct 485 ms 118580 KB Output is correct
33 Correct 513 ms 122832 KB Output is correct
34 Correct 550 ms 124956 KB Output is correct
35 Correct 525 ms 123800 KB Output is correct
36 Correct 541 ms 126824 KB Output is correct
37 Correct 493 ms 118784 KB Output is correct
38 Correct 888 ms 131400 KB Output is correct
39 Correct 850 ms 126688 KB Output is correct
40 Correct 884 ms 132076 KB Output is correct
41 Correct 875 ms 131828 KB Output is correct
42 Correct 928 ms 129552 KB Output is correct
43 Correct 435 ms 120424 KB Output is correct
44 Correct 378 ms 119984 KB Output is correct
45 Correct 351 ms 119880 KB Output is correct
46 Correct 383 ms 123400 KB Output is correct
47 Correct 802 ms 124796 KB Output is correct
48 Correct 853 ms 127660 KB Output is correct
49 Correct 850 ms 124784 KB Output is correct
50 Correct 911 ms 132552 KB Output is correct
51 Correct 328 ms 123708 KB Output is correct
52 Correct 253 ms 125300 KB Output is correct
53 Correct 315 ms 123884 KB Output is correct