Submission #1071744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071744		_rain_	Railway Trip 2 (JOI22_ho_t4)	C++14	36 / 100	92 ms	44884 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
int n,k,m,q,lim;
int stl[N][25],str[N][25],fl[N][25],fr[N][25],lf[N],rt[N];
int lmn[N],lmx[N],rmn[N],rmx[N];
int Min(int a,int b){return lf[a]<lf[b]?a:b;}
int Max(int a,int b){return rt[a]>rt[b]?a:b;}
int queryl(int l,int r){
	int lg=std::__lg(r-l+1);
	return min(stl[l][lg],stl[r-(1<<lg)+1][lg]);
}
int queryr(int l,int r){
	int lg=std::__lg(r-l+1);
	return max(str[l][lg],str[r-(1<<lg)+1][lg]);
}
int queryL(int l,int r){
	int lg=std::__lg(r-l+1);
	return Min(stl[l][lg],stl[r-(1<<lg)+1][lg]);
}
int queryR(int l,int r){
	int lg=std::__lg(r-l+1);
	return Max(str[l][lg],str[r-(1<<lg)+1][lg]);
}
void query(int s,int t){
	int l=s,r=s,res=1;
	if(lf[s]>t||rt[s]<t){
		for(int j=lim;j>=0;j--){
			int L=Min(Min(fl[lmn[l]][j],fl[rmn[r]][j]),Min(fl[lmx[l]][j],fl[rmx[r]][j]));
			int R=Max(Max(fr[lmn[l]][j],fr[rmn[r]][j]),Max(fr[lmx[l]][j],fr[rmx[r]][j]));
			if(lf[L]>t||rt[R]<t) l=L,r=R,res+=(1<<j);
		}
		res++;
	}
	cout<<(res>n?-1:res)<<"\n";
}
signed main(){
	std::ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>k>>m;
	memset(stl,0x3f,sizeof(stl));
	for(int i=1,a,b;i<=m;i++){
		cin>>a>>b;
		if(a>b) stl[a][0]=min(stl[a][0],b);
		else str[a][0]=max(str[a][0],b);
	}
	for(int j=1;(1<<j)<=n;j++)
	for(int i=1;i+(1<<j)-1<=n;i++){
		stl[i][j]=min(stl[i][j-1],stl[i+(1<<(j-1))][j-1]);
		str[i][j]=max(str[i][j-1],str[i+(1<<(j-1))][j-1]);
	}
	for(int i=1;i<=n;i++){
		lf[i]=min(i,queryl(i,min(i+k-1,n)));
		rt[i]=max(i,queryr(max(i-k+1,1),i));
		stl[i][0]=str[i][0]=i;
	}
	for(int j=1;(1<<j)<=n;j++)
	for(int i=1;i+(1<<j)-1<=n;i++){
		stl[i][j]=Min(stl[i][j-1],stl[i+(1<<(j-1))][j-1]);
		str[i][j]=Max(str[i][j-1],str[i+(1<<(j-1))][j-1]);
	}
	for(int i=1;i<=n;i++){
		fl[i][0]=fr[i][0]=i;
		lmn[i]=lf[i];
		lmx[i]=i;
		rmn[i]=i;
		rmx[i]=rt[i];
	}
	for(int j=1;(1<<j)<=n;j++,lim++){
		for(int i=1;i<=n;i++){
			int l=fl[i][j-1],r=fr[i][j-1];
			fl[i][j]=Min(Min(fl[lmn[l]][j-1],fl[rmn[r]][j-1]),Min(fl[lmx[l]][j-1],fl[rmx[r]][j-1]));
			fr[i][j]=Max(Max(fr[lmn[l]][j-1],fr[rmn[r]][j-1]),Max(fr[lmx[l]][j-1],fr[rmx[r]][j-1]));
			// cout<<fl[i][j]<<" "<<fr[i][j]<<"\n";
		}
	}
	cin >>q;
	while(q--){
		int s , t; cin >> s >> t;
		query(s,t);
	}
	return 0;
}
//ggghurjv

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13