Submission #1015917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015917		huyboy	Railway Trip 2 (JOI22_ho_t4)	C++17	0 / 100	2065 ms	25476 KiB

Main

/*
 
author : abushbandit
contest : ---
 
*/
 
#include "bits/stdc++.h"

using namespace std;

#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define ff first
#define ss second

const int INF = 1e18;
const int p = 37,m = 1e9 + 11;
const int p1 = 101,m1 = 1e9 + 7;
const int N = 1e5 + 1;

pair<int,int> t[N * 4];
int lazy[N * 4];

pair<int,int> getmax(pair<int,int> a,pair<int,int> b){

	if(a.ff > b.ff){
		return a;
	} else if(a.ff < b.ff){
		return b;
	} else{
		if(a.ss < b.ss){
			return b;
		} else{
			return a;
		}
	}
	
}

void push(int v,int tl,int tr){

	if(!lazy[v]) return;
	if(tl != tr){
		lazy[v * 2] = max(lazy[v],lazy[v * 2]);
		lazy[v * 2 + 1] = max(lazy[v],lazy[v * 2 + 1]);
	}
	t[v] = getmax(t[v],{lazy[v],tr});
	lazy[v] = 0;
}

void update(int l,int r,int val,int v,int tl,int tr){
	push(v,tl,tr);
	if(l <= tl && tr <= r){
		lazy[v] = val;
		push(v,tl,tr);
		return;
	}
	if(l > tr || tl > r){
		return;
	}
	int tm = (tl + tr) >> 1;
	update(l,r,val,v * 2,tl,tm);
	update(l,r,val,v * 2 + 1,tm + 1,tr);
	t[v] = getmax(t[v * 2],t[v * 2 + 1]);
}

pair<int,int> get(int l,int r,int v,int tl,int tr){
	
	push(v,tl,tr);
	if(l <= tl && tr <= r){
		return t[v];
	}
	if(l > tr || tl > r){
		return {0,0};
	}
	int tm = (tl + tr) >> 1;
	return getmax(get(l,r,v * 2,tl,tm),get(l,r,v * 2 + 1,tm + 1,tr));
	
}

pair<int,int> getmin(pair<int,int> a,pair<int,int> b){

	if(a.ff < b.ff){
		return a;
	} else if(a.ff > b.ff){
		return b;
	} else{
		if(a.ss > b.ss){
			return b;
		} else{
			return a;
		}
	}
	
}

pair<int,int> tdown[N * 4];
int lazy1[N * 4];

void push1(int v,int tl,int tr){

	if(lazy1[v] == INF) return;
	if(tl != tr){
		lazy1[v * 2] = min(lazy1[v],lazy1[v * 2]);
		lazy1[v * 2 + 1] = min(lazy1[v],lazy1[v * 2 + 1]);
	}
	tdown[v] = getmin(tdown[v],{lazy1[v],tl});
	lazy1[v] = INF;
}

void update1(int l,int r,int val,int v,int tl,int tr){
	push1(v,tl,tr);
	if(l <= tl && tr <= r){
		lazy1[v] = val;
		push1(v,tl,tr);
		return;
	}
	if(l > tr || tl > r){
		return;
	}
	int tm = (tl + tr) >> 1;
	update1(l,r,val,v * 2,tl,tm);
	update1(l,r,val,v * 2 + 1,tm + 1,tr);
	tdown[v] = getmin(tdown[v * 2],tdown[v * 2 + 1]);
}

pair<int,int> get1(int l,int r,int v,int tl,int tr){
	
	push1(v,tl,tr);
	if(l <= tl && tr <= r){
		return tdown[v];
	}
	if(l > tr || tl > r){
		return {INF,INF};
	}
	int tm = (tl + tr) >> 1;
	return getmin(get1(l,r,v * 2,tl,tm),get1(l,r,v * 2 + 1,tm + 1,tr));
	
}

void solve() {
	for(int i = 0;i < N * 4;i++){
		tdown[i] = {INF,INF};
		lazy1[i] = INF;
		t[i] = {0,0};
	}
	
	int n,k;
	cin >> n >> k;
	int m;
	cin >> m;
	vector<int> up(n + 1,-INF);
	vector<int> down(n + 1,INF);
	for(int i = 0;i < m;i++){
		int a,b;
		cin >> a >> b;
		if(a < b){
			up[a] = max(up[a],b);
		} else{
			down[a] = min(down[a],b);
		}
	}
	for(int j = 1;j <= n;j++){
		if(up[j] != -INF){
			update(j,min(j + k - 1,up[j] - 1),up[j],1,1,n);
		}
		if(down[j] != INF){
			update1(max(j - k +  1,down[j] + 1),j,down[j],1,1,n);
		}
	}
	int mx[n + 1],mn[n + 1];
	for(int i = 1;i <= n;i++){
		mx[i] = get(i,i,1,1,n).ff;
		mn[i] = get1(i,i,1,1,n).ff;
	}
	int q;
	cin >> q;
	for(int i = 0;i < q;i++){
		int a,b;
		cin >> a >> b;
		queue<int> q;
		q.push(a);
		vector<int> dis(n + 1,INF);
		int ans = -1;
		dis[a] = 0;
		while(!q.empty()){
			int top = q.front();
			q.pop();
			int to1 = mx[top];
			int to2 = mn[top];
			if(a < b && to1 >= b){
				ans = dis[top] + 1;
				break;
			}
			if(a > b && to2 <= b){
				ans = dis[top] + 1;
				break;
			}
			if(to1 != 0)
				to1 = get(top,to1,1,1,n).ss;
			if(to2 != INF)
				to2 = get1(to2,top,1,1,n).ss;
			if(to1 != 0 && dis[to1] > dis[top] + 1){
				dis[to1] = dis[top] + 1;
				q.push(to1);
			} 
			if(to2 != INF && dis[to2] > dis[top] + 1){
				dis[to2] = dis[top] + 1;
				q.push(to2);
			}
		}
		cout << ans << "\n";
	}
	
	
}

signed main() {
	
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	
	int t = 1;
	//~ cin >> t;
	while(t--){
		solve();
	}
 
}

	

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