Submission #1264800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264800		kustov_vadim_533	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	598 ms	44792 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef unsigned long long ull;

#define len(v) (int)((v).size())

const int LGN = 17;
const int N = 1 << LGN;

pair<int, int> tree[LGN][N << 1];

pair<int, int> merge(pair<int, int> &a, pair<int, int> &b){
	return {min(a.first, b.first), max(a.second, b.second)};
}

void build(int k, int v, int l, int r, vector<pair<int, int>> &a){
	if (r - l == 1){
		tree[k][v] = a[l];
		return;
	}
	int m = (l + r) / 2;
	build(k, v * 2, l, m, a);
	build(k, v * 2 + 1, m, r, a);
	tree[k][v] = merge(tree[k][v * 2], tree[k][v * 2 + 1]);
}

const int inf = 1e9;

pair<int, int> sum(int k, int v, int l, int r, int ql, int qr){
	if (l >= qr || ql >= r) return {inf, -inf};
	if (l >= ql && r <= qr) return tree[k][v];
	int m = (l + r) / 2;
	pair<int, int> r1 = sum(k, v * 2, l, m, ql, qr);
	pair<int, int> r2 = sum(k, v * 2 + 1, m, r, ql, qr);
	return merge(r1, r2);
}

struct event{
	int i, tp;
	event(int i, int tp) : i(i), tp(tp){}
};

void solve() {
	int n, k, m;
	cin >> n >> k >> m;

	vector<event> evs;

	for (int i = 0; i < m; ++i){
		int x, y;
		cin >> x >> y;

		--x, --y;

		if (x < y){
			evs.emplace_back(x, y + 1);
			evs.emplace_back(min(x + k - 1, y), -y - 1);
		}
		else{
			evs.emplace_back(max(y, x - k + 1), y + 1);
			evs.emplace_back(x, -y - 1);
		}
	}

	vector<pair<int, int>> a(n);
	for (int i = 0; i < n; ++i){
		evs.emplace_back(i, 0);
		a[i] = {i, i};

	}
	sort(evs.begin(), evs.end(), [&](event x, event y){
		if (x.i != y.i) return x.i < y.i;
		return x.tp > y.tp;
	});

	multiset<int> s;
	for (event ev : evs){
		if (ev.tp == 0){
			if (!s.empty()){
				a[ev.i].first = min(a[ev.i].first, *s.begin());
				a[ev.i].second = max(a[ev.i].second, *(--s.end()));
			}
		}
		else if (ev.tp > 0){
			s.insert(ev.tp - 1);
		}
		else{
			s.erase(s.find(-(ev.tp + 1)));
		}
	}

	int q;
	cin >> q;

	build(0, 1, 0, n, a);
	for (int j = 1; j < LGN; ++j){
		for (int i = 0; i < n; ++i){
			a[i] = sum(j - 1, 1, 0, n, a[i].first, a[i].second + 1);
		}
		build(j, 1, 0, n, a);
	}

	for (int i = 0; i < q; ++i){
		int x, y;
		cin >> x >> y;

		--x, --y;

		if (x == y) {
			cout << "0\n";
			continue;
		}

		int ans = 0;
		pair<int, int> cr = {x, x};
		for (int j = LGN - 1; j >= 0; --j){
			pair<int, int> nw = sum(j, 1, 0, n, cr.first, cr.second + 1);
			if (nw.first <= y && y <= nw.second){
				continue;
			} 
			ans += (1 << j);
			cr = nw;
		}

		cr = sum(0, 1, 0, n, cr.first, cr.second + 1);

		if (cr.first <= y && y <= cr.second){
			cout << ans + 1 << '\n';
		}
		else{
			cout << "-1\n";
		}
	}

}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout.precision(60);

	int t = 1;
//	cin >> t;

	while (t--) {
		solve();
	}
}

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