Submission #1287201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287201		kaiboy	Railway Trip 2 (JOI22_ho_t4)	C++20	0 / 100	137 ms	30064 KiB

Main

#include <algorithm>
#include <iostream>

using namespace std;

const int  N = 100000;
const int  L = 17;
const int N_ = 1 << L;

int st_l[N_ << 1], st_r[N_ << 1], n_;
int ll[N][L], rr[N][L], pp[N][L], qq[N][L], qu_l[N], qu_r[N];

void build(int n) {
	for (n_ = 1; n_ < n; n_ <<= 1)
		;
	for (int i = 1; i < n_ << 1; i++)
		st_l[i] = n, st_r[i] = -1;
}

void update_l(int l, int r, int a) {
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if (l & 1)
			st_l[l] = min(st_l[l], a), l++;
		if (!(r & 1))
			st_l[r] = min(st_l[r], a), r--;
	}
}

void update_r(int l, int r, int a) {
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if (l & 1)
			st_r[l] = max(st_r[l], a), l++;
		if (!(r & 1))
			st_r[r] = max(st_r[r], a), r--;
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, k, m; cin >> n >> k >> m;
	build(n);
	while (m--) {
		int i, j; cin >> i >> j, i--, j--;
		if (i < j)
			update_r(i, min(i + k, j) - 1, j);
		else
			update_l(max(i - k, j) + 1, i, j);
	}
	for (int i = 1; i < n_; i++) {
		int l = i << 1, r = l ^ 1;
		st_l[l] = min(st_l[l], st_l[i]);
		st_l[r] = min(st_l[r], st_l[i]);
		st_r[l] = max(st_r[l], st_r[i]);
		st_r[r] = max(st_r[r], st_r[i]);
	}
	for (int i = 0; i < n; i++) {
		ll[i][0] = min(st_l[i + n_], i);
		rr[i][0] = max(st_r[i + n_], i);
	}
	for (int cnt_l = 0, cnt_r = 0, i = 0; i < n; i++) {
		while (cnt_l && ll[i][0] < ll[qu_l[cnt_l - 1]][0])
			cnt_l--;
		while (cnt_r && rr[i][0] > rr[qu_r[cnt_r - 1]][0])
			cnt_r--;
		qu_l[cnt_l++] = qu_r[cnt_r++] = i;
		int lower = -1, upper = cnt_l - 1;
		while (upper - lower > 1) {
			int h = lower + upper >> 1;
			if (qu_l[h] >= ll[i][0])
				upper = h;
			else
				lower = h;
		}
		pp[i][0] = qu_l[upper];
		lower = -1, upper = cnt_r - 1;
		while (upper - lower > 1) {
			int h = lower + upper >> 1;
			if (qu_r[h] >= ll[i][0])
				upper = h;
			else
				lower = h;
		}
		qq[i][0] = qu_r[upper];
	}
	for (int cnt_l = 0, cnt_r = 0, i = n - 1; i >= 0; i--) {
		while (cnt_l && ll[i][0] < ll[qu_l[cnt_l - 1]][0])
			cnt_l--;
		while (cnt_r && rr[i][0] > rr[qu_r[cnt_r - 1]][0])
			cnt_r--;
		qu_l[cnt_l++] = qu_r[cnt_r++] = i;
		int lower = -1, upper = cnt_l - 1;
		while (upper - lower > 1) {
			int h = lower + upper >> 1;
			if (qu_l[h] <= rr[i][0])
				upper = h;
			else
				lower = h;
		}
		if (ll[pp[i][0]][0] > ll[qu_l[upper]][0])
			pp[i][0] = qu_l[upper];
		lower = -1, upper = cnt_r - 1;
		while (upper - lower > 1) {
			int h = lower + upper >> 1;
			if (qu_r[h] <= rr[i][0])
				upper = h;
			else
				lower = h;
		}
		if (rr[qq[i][0]][0] < rr[qu_r[upper]][0])
			qq[i][0] = qu_r[upper];
	}
	for (int h = 0; h + 1 < L; h++)
		for (int i = 0; i < n; i++) {
			int p = pp[i][h], q = qq[i][h];
			ll[i][h + 1] = min(ll[p][h], ll[q][h]);
			rr[i][h + 1] = max(rr[p][h], rr[q][h]);
			if (ll[p][0] > ll[pp[p][h]][0])
				p = pp[p][h];
			if (rr[q][0] < rr[qq[p][h]][0])
				q = qq[p][h];
			if (ll[p][0] > ll[pp[q][h]][0])
				p = pp[q][h];
			if (rr[q][0] < rr[qq[q][h]][0])
				q = qq[q][h];
			pp[i][h + 1] = p;
			qq[i][h + 1] = q;
		}
	int tc; cin >> tc;
	while (tc--) {
		int s, t; cin >> s >> t, s--, t--;
		int x = 1, p = s, q = s;
		for (int h = L - 1; h >= 0; h--)
			if (t < min(ll[p][h], ll[q][h]) || min(rr[p][h], rr[q][h]) < t) {
				x += 1 << h;
				int p_ = p, q_ = q;
				if (ll[p_][0] > ll[pp[p][h]][0])
					p_ = pp[p][h];
				if (rr[q_][0] < rr[qq[p][h]][0])
					q_ = qq[p][h];
				if (ll[p_][0] > ll[pp[q][h]][0])
					p_ = pp[q][h];
				if (rr[q_][0] < rr[qq[q][h]][0])
					q_ = qq[q][h];
				p = p_, q = q_;
			}
		cout << (ll[p][0] <= t && t <= rr[q][0] ? x : -1) << '\n';
	}
	return 0;
}

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