Submission #1228231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228231		siewjh	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	250 ms	227224 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int lg[MAXN], spmx[17][17][MAXN], spmn[17][17][MAXN];
int N, K, M;
int query(int l, int r, bool typ, int id){
	int lgv = lg[r - l + 1];
	if (typ) return max(spmx[id][lgv][l], spmx[id][lgv][r - (1 << lgv) + 1]);
	else return min(spmn[id][lgv][l], spmn[id][lgv][r - (1 << lgv) + 1]);
}
void build(int id){
	for (int k = 1; k <= 16; k++)
		for (int i = N + 1 - (1 << k); i >= 1; i--){
			spmn[id][k][i] = min(spmn[id][k - 1][i], spmn[id][k - 1][i + (1 << (k - 1))]);
			spmx[id][k][i] = max(spmx[id][k - 1][i], spmx[id][k - 1][i + (1 << (k - 1))]);
		}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> K >> M;
	lg[1] = 0;
	for (int i = 2; i <= N; i++) lg[i] = lg[i >> 1] + 1;
	vector<vector<int>> fwv(N + 1), bwv(N + 1);
	for (int i = 0; i < M; i++){
		int a, b; cin >> a >> b;
		if (a < b){
			fwv[a].push_back(b); fwv[min(a + K, b)].push_back(-b);
		}
		else{
			bwv[a].push_back(b); bwv[max(a - K, b)].push_back(-b);
		}
	}
	multiset<int> ins;
	for (int i = 1; i <= N; i++){
		for (int x : fwv[i]){
			if (x > 0) ins.insert(x);
			else ins.erase(ins.find(-x));
		}
		spmx[0][0][i] = (ins.empty() ? i : *ins.rbegin());
	}
	ins.clear();
	for (int i = N; i >= 1; i--){
		for (int x : bwv[i]){
			if (x > 0) ins.insert(x);
			else ins.erase(ins.find(-x));
		}
		spmn[0][0][i] = (ins.empty() ? i : *ins.begin());
	}
	build(0);
	for (int k = 1; k <= 16; k++){
		for (int i = 1; i <= N; i++){
			int l = spmn[k - 1][0][i], r = spmx[k - 1][0][i];
			spmn[k][0][i] = query(l, r, 0, k - 1); spmx[k][0][i] = query(l, r, 1, k - 1);
		}
		build(k);
	}
	int Q; cin >> Q;
	while (Q--){
		int a, b; cin >> a >> b;
		int l = a, r = a, ans = 0;
		for (int k = 16; k >= 0; k--){
			int nl = query(l, r, 0, k), nr = query(l, r, 1, k);
			if (!(nl <= b && b <= nr)){
				ans += (1 << k); l = nl; r = nr;
			}
		}
		int nl = query(l, r, 0, 0), nr = query(l, r, 1, 0);
		cout << ((nl <= b && b <= nr) ? ans + 1 : -1) << '\n';
	}
}

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