oj.uz

답안 #768608

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
768608 2023-06-28T09:58:37 Z amirhoseinfar1385 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 286 ms 113024 KB 
#include<bits/stdc++.h>
using namespace std;
const long long maxn=500000+10;
vector<long long>allv[maxn];
long long mp[maxn],base=37,mod=1020023471,ps[maxn],maxa[maxn],sz,rev[maxn];
long long m,n;
string s;
long long 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(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;
	}
}

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

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,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);
	cin>>n>>m;
	for(long long i=0;i<n;i++){
		cin>>s;
		long long unnow=0;
		for(long long j=0;j<(long long)s.size();j++){
			unnow+=1ll*(s[j]-'a'+1)*mp[j]%mod;
			unnow=ww(unnow);
			allv[j+1].push_back(unnow);
		}
	}
	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;
	sz=(long long)s.size();
	for(long long j=0;j<(long long)s.size();j++){
		unnow+=1ll*(s[j]-'a'+1)*mp[j]%mod;
		unnow=ww(unnow);
		ps[j+1]=unnow;
	}
	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,pors(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

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 98100 KB Output is correct
2 Correct 128 ms 103932 KB Output is correct
3 Correct 135 ms 102084 KB Output is correct
4 Correct 135 ms 103148 KB Output is correct
5 Correct 132 ms 102884 KB Output is correct
6 Correct 148 ms 103756 KB Output is correct
7 Correct 157 ms 105320 KB Output is correct
8 Correct 137 ms 104056 KB Output is correct
9 Correct 133 ms 103756 KB Output is correct
10 Correct 116 ms 100264 KB Output is correct
11 Correct 126 ms 113024 KB Output is correct
12 Correct 106 ms 105432 KB Output is correct
13 Correct 136 ms 109600 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 286 ms 109040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 98100 KB Output is correct
2 Correct 128 ms 103932 KB Output is correct
3 Correct 135 ms 102084 KB Output is correct
4 Correct 135 ms 103148 KB Output is correct
5 Correct 132 ms 102884 KB Output is correct
6 Correct 148 ms 103756 KB Output is correct
7 Correct 157 ms 105320 KB Output is correct
8 Correct 137 ms 104056 KB Output is correct
9 Correct 133 ms 103756 KB Output is correct
10 Correct 116 ms 100264 KB Output is correct
11 Correct 126 ms 113024 KB Output is correct
12 Correct 106 ms 105432 KB Output is correct
13 Correct 136 ms 109600 KB Output is correct
14 Incorrect 286 ms 109040 KB Output isn't correct
15 Halted 0 ms 0 KB -