Submission #744789

#	Time	Username	Problem	Language	Result	Execution time	Memory
744789		ethening	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	623 ms	76596 KiB

Main

#include "bits/stdc++.h"
#include <valarray>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

#define DEBUG 1
#define MULTI_TEST 0

struct Node {
	int l{}, r{};
	Node() { this->l = 1e9, this->r = -1; }
	Node(int l, int r) { this->l = l, this->r = r; }
	Node(int x) { this->l = x, this->r = x; }
	Node operator+(const Node& other) {
		return Node(min(this->l, other.l), max(this->r, other.r));
	}
};

struct SegmentTree {
	vector<Node> leafs;
	vector<Node> node;
	void build(int n, vector<Node>& vec) {
		leafs = vec;
		node.resize(4 * n);
		auto build = [&](auto&& build, int id, int l, int r) -> void {
			if (l == r) node[id] = vec[l];
			else {
				int mid = (l + r) / 2;
				build(build, id * 2, l, mid);
				build(build, id * 2 + 1, mid + 1, r);
				node[id] = node[id * 2] + node[id * 2 + 1];
			}
		};
		build(build, 1, 0, n - 1);
	}

	void update(int id, int l, int r, int pos, int val) {
		if (l == r) node[id] = val;
		else {
			int mid = (l + r) / 2;
			if (pos <= mid) update(id * 2, l, mid, pos, val);
			else update(id * 2 + 1, mid + 1, r, pos, val);
		}
	}

	Node query(int id, int l, int r, int L, int R) {
		if (l > R || r < L) return Node();
		else if (L <= l && r <= R) return node[id];
		else {
			int mid = (l + r) / 2;
			return query(id * 2, l, mid, L, R) + query(id * 2 + 1, mid + 1, r, L, R);
		}
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, k;
	cin >> n >> k;
	int m;
	cin >> m;

	int lgn = 0;
	while (1 << (lgn + 1) <= n) {
		++lgn;
	}
	++lgn;
	++lgn;

	vector<SegmentTree> segtree(lgn);
	
	vector<int> right_train(n, -1);
	vector<int> left_train(n, -1);

	for (int i = 0; i < m; i++) {
		int ai{}, bi{};
		cin >> ai >> bi;
		--ai, --bi;
		if (bi > ai) {
			if (right_train[ai] == -1) right_train[ai] = bi;
			else right_train[ai] = max(right_train[ai], bi);
		}
		else {
			if (left_train[ai] == -1) left_train[ai] = bi;
			else left_train[ai] = min(left_train[ai], bi);
		}
	}

	vector<Node> initial_step(n);
	for (int i = 0; i < n; i++) initial_step[i] = Node(i);

	deque<pair<int, int>> Q;
	for (int i = 0; i < n; i++) {
		if (right_train[i] != -1) {
			while (!Q.empty() && right_train[i] > Q.back().second) Q.pop_back();
			Q.push_back({i, right_train[i]});
		}
		while (!Q.empty() && Q.front().first + k <= i) Q.pop_front();
		while (!Q.empty() && Q.front().second <= i) Q.pop_front();
		if (!Q.empty()) initial_step[i].r = Q.front().second;
	}
	Q.clear();
	for (int i = n - 1; i >= 0; i--) {
		if (left_train[i] != -1) {
			while (!Q.empty() && left_train[i] < Q.back().second) Q.pop_back();
			Q.push_back({i, left_train[i]});
		}
		while (!Q.empty() && Q.front().first - k >= i) Q.pop_front();
		while (!Q.empty() && Q.front().second >= i) Q.pop_front();
		if (!Q.empty()) initial_step[i].l = Q.front().second;
	}

	segtree[0].build(n, initial_step);
	for (int i = 1; i < lgn; i++) {
		vector<Node> new_step(n);
		for (int j = 0; j < n; j++) {
			new_step[j] = segtree[i - 1].leafs[j];
			new_step[j] = segtree[i - 1].query(1, 0, n - 1, new_step[j].l, new_step[j].r);
		}
		segtree[i].build(n, new_step);
	}

	// for (int i = 0; i < lgn; i++) {
	// 	cout << "Step " << (1 << i) << "\n";
	// 	for (int j = 0; j < n; j++) {
	// 		cout << "Pos " << j << " : " << segtree[i].leafs[j].l << " " << segtree[i].leafs[j].r << endl;
	// 	}
	// }

	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int si{}, ti{};
		cin >> si >> ti;
		--si, --ti;

		Node end_range = segtree[lgn - 1].leafs[si];
		if (end_range.l > ti || end_range.r < ti) {
			cout << -1 << "\n";
			continue;
		}

		int ans = 1 << (lgn - 1);
		int cur = 0;
		Node cur_range = {si, si};
		for (int i = lgn - 1; i >= 0; i--) {
			Node new_range = segtree[i].query(1, 0, n - 1, cur_range.l, cur_range.r);
			if (new_range.l > ti || new_range.r < ti) { // not reach
				cur += 1 << i;
				cur_range = new_range;
			}
			else { // reach
				ans = min(ans, cur + (1 << i));
			}
		}
		cout << ans << "\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