Submission #586913

#	Time	Username	Problem	Language	Result	Execution time	Memory
586913		dutinmeow	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	555 ms	50504 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int $L = 20;

int main() {
	int N, K, M;
	cin >> N >> K >> M;

	array<vector<int>, $L> lb, rb;
	lb.fill(vector<int>(2 * N, -1));
	rb.fill(vector<int>(2 * N, -1));

	vector<int> A(M), B(M);
	for (int i = 0; i < M; i++) {
		cin >> A[i] >> B[i];
		A[i]--, B[i]--;
	}
	
	multiset<int> mse;
	vector<vector<int>> ins(N), era(N);

	for (int i = 0; i < M; i++) {
		if (A[i] > B[i]) {
			ins[A[i]].push_back(B[i]);
			era[max(A[i] - K + 1, B[i] + 1)].push_back(B[i]);
		}
	}
	for (int i = N - 1; i >= 0; i--) {
		for (int k : ins[i])
			mse.insert(k);
		ins[i].clear();
		lb[0][i + N] = min(i, mse.empty() ? N : *mse.begin());
		for (int k : era[i])
			mse.erase(mse.lower_bound(k));
		era[i].clear();
	}
	assert(mse.empty());

	for (int i = 0; i < M; i++) {
		if (A[i] < B[i]) {
			ins[A[i]].push_back(B[i]);
			era[min(A[i] + K - 1, B[i] - 1)].push_back(B[i]);
		} 
	}
	for (int i = 0; i < N; i++) {
		for (int k : ins[i])
			mse.insert(k);
		ins[i].clear();
		rb[0][i + N] = max(i, mse.empty() ? 0 : *mse.rbegin());
		for (int k : era[i])
			mse.erase(mse.lower_bound(k));
		era[i].clear();
	}
	assert(mse.empty());

	for (int b = 1; b < $L; b++) {
		for (int i = N - 1; i >= 1; i--) {
			lb[b - 1][i] = min(lb[b - 1][i * 2], lb[b - 1][i * 2 + 1]);
			rb[b - 1][i] = max(rb[b - 1][i * 2], rb[b - 1][i * 2 + 1]);
		}
		for (int i = 0; i < N; i++) {
			int l = lb[b - 1][i + N], r = rb[b - 1][i + N];
			int retl = N, retr = 0;
			for (l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
				if (l & 1) {
					retl = min(retl, lb[b - 1][l]);
					retr = max(retr, rb[b - 1][l]);
					l++;
				}
				if (r & 1) {
					r--;
					retl = min(retl, lb[b - 1][r]);
					retr = max(retr, rb[b - 1][r]);
				}
			} 
			lb[b][i + N] = retl, rb[b][i + N] = retr;
		}
	}

	int Q;
	cin >> Q;
	while (Q--) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		int l = u, r = u;
		if (v < lb[$L - 1][u + N] || rb[$L - 1][u + N] < v) {
			cout << -1 << '\n';
		} else {
			int ans = 0;
			for (int b = $L - 1; b >= 0; b--) {
				int retl = N, retr = 0;
				for (int ll = l + N, rr = r + N + 1; ll < rr; ll >>= 1, rr >>= 1) {
					if (ll & 1) {
						retl = min(retl, lb[b][ll]);
						retr = max(retr, rb[b][ll]);
						ll++;
					}
					if (rr & 1) {
						rr--;
						retl = min(retl, lb[b][rr]);
						retr = max(retr, rb[b][rr]);
					}
				} 
				if (v < retl || retr < v) {
					l = retl, r = retr;
					ans |= (1 << b);
				}
			}
			cout << ans + 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