Submission #883492

#	Time	Username	Problem	Language	Result	Execution time	Memory
883492		Mik01aj	Railway Trip 2 (JOI22_ho_t4)	C++17	0 / 100	798 ms	72036 KiB

Main

#include <iostream>
#include <vector>
#include <map>
#include <stack>
#define ll long long
using namespace std;


const int N = 520005, K = 20;
int n, k, m, q, min_l[K][N], max_r[K][N], s = 1;

void updateR(int l, int r, int bit, int v) {
	l += s;
	r += s;
	max_r[bit][l] = max(max_r[bit][l], v);
	max_r[bit][r] = max(max_r[bit][r], v);
	while (l + 1 < r) {
		if (!(l & 1)) {
			max_r[bit][l + 1] = max(max_r[bit][l + 1], v);
		}
		if (r & 1) {
			max_r[bit][r - 1] = max(max_r[bit][r - 1], v);
		}
		r >>= 1;
		l >>= 1;
	}
	while (l > 0) {
		max_r[bit][l] = max(max_r[bit][l], v);
		l >>= 1;
	}
}
void updateL(int l, int r, int bit, int v) {
	l += s;
	r += s;
	min_l[bit][l] = min(min_l[bit][l], v);
	min_l[bit][r] = min(min_l[bit][r], v);
	while (l + 1 < r) {
		if (!(l & 1)) {
			min_l[bit][l + 1] = min(min_l[bit][l + 1], v);
		}
		if (r & 1) {
			min_l[bit][r - 1] = min(min_l[bit][r - 1], v);
		}
		r >>= 1;
		l >>= 1;
	}
	while (l > 0) {
		min_l[bit][l] = min(min_l[bit][l], v);
		l >>= 1;
	}
}
int findR(int l, int r, int bit) {
	l += s;
	r += s;
	int maxi = max(max_r[bit][l], max_r[bit][r]);
	while (l + 1 < r) {
		if (!(l & 1)) {
			maxi = max(maxi, max_r[bit][l + 1]);
		}
		if (r & 1) {
			maxi = max(maxi, max_r[bit][r - 1]);
		}
		r >>= 1;
		l >>= 1;
	}
	return maxi;
}
int findL(int l, int r, int bit) {
	l += s;
	r += s;
	int mini = min(min_l[bit][l], min_l[bit][r]);
	while (l + 1 < r) {
		if (!(l & 1)) {
			mini = min(mini, min_l[bit][l + 1]);
		}
		if (r & 1) {
			mini = min(mini, min_l[bit][r - 1]);
		}
		r >>= 1;
		l >>= 1;
	}
	return mini;
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> n >> k >> m;
	while (s <= n)
		s <<= 1;
	for (int j = 0; j < K; j++)
		for (int i = 1; i <= n; i++)
			min_l[j][i + s] = max_r[j][i + s] = i;
	for (int i = 0; i < K; i++)
		min_l[i][s] = 1; 
	for (int j = 0; j < K; j++)
		for (int i = s + n + 1; i < 2 * s; i++)
			min_l[j][i] = n;
	for (int j = 0; j < K; j++)
		for (int i = s - 1; i >=0; i--) {
			min_l[j][i] = min(min_l[j][i * 2], min_l[j][i * 2 + 1]);
			max_r[j][i] = max(max_r[j][i * 2], max_r[j][i * 2 + 1]);
		}
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		if (a < b) {
			updateR(a, min(a + k - 1, b), 0, b);
		}
		else
		{
			updateL(max(b, a - k + 1), a, 0, b);
		}
	}
	for (int j = 1; j < K; j++) {
		for (int i = 1; i < 2 * s; i++) {
			min_l[j][i] = findL(min_l[j - 1][i], max_r[j - 1][i], j - 1);
			max_r[j][i] = findR(min_l[j - 1][i], max_r[j - 1][i], j - 1);
		}
	}
	cin >> q;
	for (; q--;) {
		int a, b;
		cin >> a >> b;
		int l = a, r = a, res = 0;
		bool ok = 0;
		for (int i = K - 1; i >= 0; i--) {
			int new_l = findL(l, r, i), new_r = findR(l, r, i);
			if (new_l <= b && new_r >= b)
				ok = 1;
			else {
				res += (1 << i);
				l = new_l;
				r = new_r;
			}
		}
		if (ok)
			cout << res + 1 << '\n';
		else
			cout << -1 << '\n';
	}
}

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