Submission #1217577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217577		trimkus	Railway Trip 2 (JOI22_ho_t4)	C++20	35 / 100	684 ms	56636 KiB

Main

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

struct RMQ {
	vector<int> tree;
	int n;
	void init(int n) {
		this->n = n;
		tree = vector<int>(4 * n, -1);
	}
	void update(int i, int l, int r, int qp, int val) {
		if (l == r) {
			tree[i] = max(tree[i], 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);
		tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
	}
	void update(int qp, int val) {
		update(1, 1, n, qp, val);
	}
	int query(int i, int l, int r, int ql, int qr) {
		if (l > qr || r < ql) return -1;
		if (ql <= l && r <= qr) return tree[i];
		int m = (l + r) / 2;
		return max(query(i * 2, l, m, ql, qr), query(i * 2 + 1, m + 1, r, ql, qr));
	}
	int query(int ql, int qr) {
		return query(1, 1, n, ql, qr);
	}
};


int main() {
	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] = -1;
		}
	}
	vector<vector<array<int, 2>>> events(n + 1);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		assert(a < b);
		int till = min(b, a + k);
		events[a].push_back({b, till});
		events[till].push_back({-b, till});
	}
	multiset<pair<int, int>> mt;
	for (int j = 1; j <= n; ++j) {
		for (auto& u : events[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());
			lift[j][0] = it->first;
		}
	}
	//~ for (int i = 1; i <= n; ++i) {
		//~ cerr << lift[i][0] << " ";
	//~ }
	//~ cerr << "\n";
	vector<RMQ> lifts(LOG + 1);
	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(j, lift[j][i]);
		}
	}
	//~ for (int i = 1; i <= n; ++i) {
		//~ cerr << lifts[1].query(i, i) << " ";
	//~ }
	//~ cerr << "\n";
	//~ for (int i = 1; i <= n; ++i) {
		//~ cerr << lifts[2].query(i, i) << " ";
	//~ }
	//~ cerr << "\n";
	int q;
	cin >> q;
	while (q--) {
		int a, b;
		cin >> a >> b;
		assert(a < b);
		int res = 0;
		int nxt = a;
		for (int i = LOG; i >= 0; --i) {
			int NEXT = lifts[i].query(a, nxt);
			//~ cerr << a << " -> " << nxt << "\n";
			if (NEXT > nxt && NEXT < b) {
				nxt = NEXT;
				res += (1 << i);
			}
		}
		res += 1;
		a = lifts[0].query(a, nxt);
		//~ cerr << a << " " << b << " = ";
		if (a < b) {
			cout << "-1\n";
			continue;
		}
		cout << res << "\n";
	}
	
}

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