Submission #883583

#	Time	Username	Problem	Language	Result	Execution time	Memory
883583		Mik01aj	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	675 ms	88156 KiB

Main

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


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

void updateR(int l, int r, int v) {
	l += s;
	r += s;
	treer[l] = max(treer[l], v);
	treer[r] = max(treer[r], v);
	while (l + 1 < r) {
		if (!(l & 1)) {
			treer[l + 1] = max(treer[l + 1], v);
		}
		if (r & 1) {
			treer[r - 1] = max(treer[r - 1], v);
		}
		r >>= 1;
		l >>= 1;
	}
}
void updateL(int l, int r, int v) {
	l += s;
	r += s;
	treel[l] = min(treel[l], v);
	treel[r] = min(treel[r], v);
	while (l + 1 < r) {
		if (!(l & 1)) {
			treel[l + 1] = min(treel[l + 1], v);
		}
		if (r & 1) {
			treel[r - 1] = min(treel[r - 1], v);
		}
		r >>= 1;
		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 fl(int i) {
	i += s;
	int mini = inf;
	while (i > 0) {
		mini = min(mini, treel[i]);
		i >>= 1;
	}
	return mini;
}
int fr(int i) {
	i += s;
	int maxi = 0;
	while (i > 0) {
		maxi = max(maxi, treer[i]);
		i >>= 1;
	}
	return maxi;
}

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 i = 0; i <= 2 * s; i++) {
		treel[i] = inf;
		treer[i] = 0;
	}
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		if (a < b) {
			updateR(a, min(a + k - 1, b), b);
		}
		else
		{
			updateL(max(b, a - k + 1), a, b);
		}
	}
	for (int i = 0; i <= n; i++) {
		min_l[0][i + s] = min(i, fl(i));
		max_r[0][i + s] = max(i, fr(i));
	}
	for (int i = s - 1; i > 0; i--) {
		min_l[0][i] = min(min_l[0][2 * i], min_l[0][2 * i + 1]);
		max_r[0][i] = max(max_r[0][2 * i], max_r[0][2 * i + 1]);
	}
	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: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13