Submission #1217875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217875		trimkus	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	773 ms	102908 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = double;
const int LOG = 21;
const int MAXM = 1e5;
pair<int, int> lift[MAXM + 1][LOG + 2];

struct RMQ {
	vector<pair<int, int>> tree;
	int n;
	void init(int n) {
		this->n = n;
		tree = vector<pair<int, int>>(4 * n, {INT_MAX, INT_MIN});
	}
	void update_node(pair<int, int>& x, pair<int, int> y, pair<int, int> z) {
		x.first = min({x.first, y.first, z.first});
		x.second = max({x.second, y.second, z.second});
	}
	void update(int i, int l, int r, int qp, pair<int, int> val) {
		if (l == r) {
			update_node(tree[i], val, val);
			return;
		}
		int m = (l + r) / 2;
		if (qp <= m) update(i * 2, l, m, qp, val);
		else update(i * 2 + 1, m + 1, r, qp, val);
		update_node(tree[i], tree[i * 2], tree[i * 2 + 1]);
	}
	void update(int qp, pair<int, int> val) {
		update(1, 1, n, qp, val);
	}
	pair<int, int> query(int i, int l, int r, int ql, int qr) {
		if (l > qr || r < ql) return {INT_MAX, INT_MIN};
		if (ql <= l && r <= qr) return tree[i];
		int m = (l + r) / 2;
		pair<int, int> res = {INT_MAX, INT_MIN};
		update_node(res, query(i * 2, l, m, ql, qr), query(i * 2 + 1, m + 1, r, ql, qr));
		return res;
	}
	pair<int, int> query(int ql, int qr) {
		return query(1, 1, n, ql, qr);
	}
};

void combine(pair<int, int>& x, pair<int, int> y) {
	x.first = min({x.first, y.first});
	x.second = max({x.second, y.second});
}

int main() {
	//~ ofstream cout("out.txt");
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, k, m;
	cin >> n >> k >> m;
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= LOG; ++j) {
			lift[i][j] = {INT_MAX, INT_MIN};
		}
	}
	vector<vector<array<int, 2>>> right(n + 1), left(n + 1);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		if (a < b) {
			int till = min(b, a + k);
			right[a].push_back({b, till});
			right[till].push_back({-b, till});
		} else {
			int till = max(b, a - k);
			left[a].push_back({b, till});
			left[till].push_back({-b, till});
		}
	}
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= LOG; ++j) {
			lift[i][j] = {INT_MAX, INT_MIN};
		}
	}
	vector<RMQ> lifts(LOG + 1);
	{
		multiset<pair<int, int>> mt;
		for (int j = 1; j <= n; ++j) {
			for (auto& u : right[j]) {
				if (u[0] < 0) {
					mt.erase(mt.find({-u[0], u[1]}));
				} else {
					mt.insert({u[0], u[1]});
				}
			}
			if (mt.size() > 0) {
				auto it = prev(mt.end());
				//~ cerr << j << " " << it->first << "\n";
				combine(lift[j][0], {j, it->first});
			}
		}
		mt.clear();
		for (int j = n; j >= 1; --j) {
			for (auto& u : left[j]) {
				if (u[0] < 0) {
					mt.erase(mt.find({-u[0], u[1]}));
				} else {
					mt.insert({u[0], u[1]});
				}
			}
			if (mt.size() > 0) {
				auto it = begin(mt);
				//~ cerr << j << " " << it->first << "\n";
				combine(lift[j][0], {it->first, j});
			}
		}
		//~ for (int i = 1; i <= n; ++i) {
			//~ cerr << i << " = [" << lift[i][0].first << " , " << lift[i][0].second << "]\n";
		//~ }
		for (int i = 0; i <= LOG; ++i) {
			lifts[i].init(n);
			for (int j = 1; j <= n; ++j) {
				lifts[i].update(j, lift[j][i]);
			}
			for (int j = 1; j <= n; ++j) {
				lift[j][i + 1] = lifts[i].query(lift[j][i].first, lift[j][i].second);
			}
		}
	}
	//~ for (int i = 0; i < 3; ++i) {
		//~ for (int j = 1; j <= n; ++j) {
			//~ auto inter = lifts[i].query(lift[j][i].first, lift[j][i].second);
			//~ cerr << j << " = [" << lift[j][i].first << " , " << lift[j][i].second << "]\n";
		//~ }
		//~ cerr << "\n";
	//~ }
	int q;
	cin >> q;
	while (q--) {
		int a, b;
		cin >> a >> b;
		pair<int, int> inter = {a, a};
		int res = 0;
		for (int i = LOG; i >= 0; --i) {
			pair<int, int> nxt = lifts[i].query(inter.first, inter.second);
			if (!(nxt.first <= b && b <= nxt.second)) {
				inter = nxt;
				res += (1 << i);
			}
		}
		inter = lifts[0].query(inter.first, inter.second);
		res += 1;
		if (!(inter.first <= b && b <= inter.second)) {
			cout << "-1\n";
			continue;
		}
		cout << res << "\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