Submission #1182896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182896		PieArmy	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	634 ms	54676 KiB

Main

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;

int n,k,m;
int lefs[100023],rigs[100023];
vector<int>leftmost[100023],rightmost[100023];
pair<int,int>tree[400023][18];

void it(){
	multiset<int>stl,str;
	for(int i=1;i<=n;i++){
		for(int x:rightmost[i]){
			if(x<0)str.erase(str.find(x));
			else str.insert(-x);
		}
		for(int x:leftmost[i]){
			if(x<0)stl.erase(stl.find(-x));
			else stl.insert(x);
		}
		if(str.size()){
			rigs[i]=max(rigs[i],-*str.begin());
		}
		if(stl.size()){
			lefs[i]=min(lefs[i],*stl.begin());
		}
	}
}

void build(int lg,int node=1,int left=1,int right=-1){
	if(right==-1)right=n;
	if(left==right){
		tree[node][lg].fr=lefs[left];
		tree[node][lg].sc=rigs[left];
		return;
	}
	const int mid=(left+right)>>1;
	build(lg,node*2,left,mid);
	build(lg,node*2+1,mid+1,right);
	tree[node][lg]={min(tree[node*2][lg].fr,tree[node*2+1][lg].fr),max(tree[node*2][lg].sc,tree[node*2+1][lg].sc)};
}

pair<int,int> query(int lg,int l,int r,int node=1,int left=1,int right=-1){
	if(right==-1)right=n;
	if(left>r||right<l)return {n+1,-n-1};
	if(left>=l&&right<=r)return tree[node][lg];
	const int mid=(left+right)>>1;
	pair<int,int>res1=query(lg,l,r,node*2,left,mid),res2=query(lg,l,r,node*2+1,mid+1,right);
	return {min(res1.fr,res2.fr),max(res1.sc,res2.sc)};
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>k>>m;
	for(int i=1;i<=n;i++){
		lefs[i]=i;
		rigs[i]=i;
	}
	for(int i=1;i<=m;i++){
		int a,b;cin>>a>>b;
		if(a<b){
			rightmost[a].pb(b);
			rightmost[min(a+k-1,b)+1].pb(-b);
		}
		else{
			leftmost[max(a-k+1,b)].pb(b);
			leftmost[a+1].pb(-b);
		}
	}
	it();
	build(0);
	for(int i=1;i<18;i++){
		for(int j=1;j<=n;j++){
			//cout<<lefs[j]<<":"<<rigs[j]<<" ";
			pair<int,int>p=query(i-1,lefs[j],rigs[j]);
			lefs[j]=p.fr;
			rigs[j]=p.sc;
		}
		//cout<<endl;
		build(i);
	}
	int q;cin>>q;
	while(q--){
		int s,t;cin>>s>>t;
		int l=s,r=s;
		int ans=1;
		for(int i=18-1;i>=0;i--){
			pair<int,int>p=query(i,l,r);
			if(t>=p.fr&&t<=p.sc)continue;
			ans+=(1<<i);
			l=p.fr;
			r=p.sc;
		}
		if(ans>m){
			cout<<-1;
		}
		else cout<<ans;
		cout<<endl;
	}
}

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