Submission #849760

#	Time	Username	Problem	Language	Result	Execution time	Memory
849760		qthang2k11	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	1302 ms	129100 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, lg = __lg(N) + 1;

int n, k, m, q;

struct Node {
	int l, r;
	
	Node(int l = N, int r = 0):
		l(l), r(r) {}
	
	Node operator + (const Node &other) const {
		return Node(min(l, other.l), max(r, other.r));
	}
	
	Node& operator += (const Node &other) {
		l = min(l, other.l);
		r = max(r, other.r);
		return (*this);
	}
};

struct SegmentTree {
	Node IT[N << 2], LZ[N << 2];
	
	SegmentTree() = default;
	
	void apply(int id, const Node &val) {
		IT[id] += val;
		LZ[id] += val;
	}
	
	void push(int id) {
		Node &cur = LZ[id];
		if (cur.l == N && cur.r == 0) return;
		apply(id << 1, cur);
		apply(id << 1 | 1, cur);
		cur = Node();
	}
	
	void update(int x, int y, const Node &val, int id, int l, int r) {
		if (l > y || r < x) return;
		if (x <= l && r <= y) 
			return apply(id, val);
		push(id);
		int mid = (l + r) / 2;
		update(x, y, val, id << 1, l, mid);
		update(x, y, val, id << 1 | 1, mid + 1, r);
		IT[id] = IT[id << 1] + IT[id << 1 | 1];
	}
	
	Node get(int x, int y, int id, int l, int r) {
		if (l > y || r < x) return Node();
		if (x <= l && r <= y) return IT[id];
		push(id);
		int mid = (l + r) / 2;
		return get(x, y, id << 1, l, mid) + get(x, y, id << 1 | 1, mid + 1, r);
	}
	
	inline void update(int x, int y, const Node &val) {
		update(x, y, val, 1, 1, n);
	}
	
	inline Node get(int x, int y) {
		return get(x, y, 1, 1, n);
	}
} IT[lg + 3];

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> k >> m;   
	for (int i = 1; i <= n; i++)
		IT[0].update(i, i, Node(i, i));
	for (int i = 1; i <= m; i++) {
		int l, r;
		cin >> l >> r;
		if (l <= r) {
			int p = min(l + k - 1, r);
			IT[0].update(l, p, Node(N, r));
		} else {
			int p = max(l - k + 1, r);
			IT[0].update(p, l, Node(r, 0));
		}
	}
	for (int k = 1; k <= lg; k++) {
		for (int i = 1; i <= n; i++) {
			const auto &S = IT[k - 1].get(i, i);
			IT[k].update(i, i, IT[k - 1].get(S.l, S.r));
		}
	}
	cin >> q;
	while (q--) {
		int s, t, ans = 0;
		cin >> s >> t;
		if (s == t) {
			cout << "0\n";
			continue;
		}
		Node now(s, s);
		for (int k = lg; k >= 0; k--) {
			Node cur = IT[k].get(now.l, now.r);
			if (cur.l <= t && t <= cur.r) continue;
			ans += (1 << k);
			now = cur;
		}
		now = IT[0].get(now.l, now.r);
		if (now.l <= t && t <= now.r) cout << ans + 1;
		else cout << -1;
		cout << '\n';
	}
	return 0;
}

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