Submission #1043555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043555		TAhmed33	Railway Trip 2 (JOI22_ho_t4)	C++98	100 / 100	939 ms	168020 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 25;
const int B = 19;
#define mid ((l + r) >> 1)
#define tl (node << 1)
#define tr (node << 1 | 1)
struct SegmentTree {
	int mx[MAXN << 2], mn[MAXN << 2];
	void pull (int l, int r, int node) {
		mn[node] = min(mn[tl], mn[tr]);
		mx[node] = max(mx[tl], mx[tr]);
	}
	void build (int l, int r, int node) {
		if (l == r) {
			mn[node] = mx[node] = l;
			return;
		}
		build(l, mid, tl); build(mid + 1, r, tr);
		pull(l, r, node);
	}
	void update (int l, int r, int a, int b, int node) {
		if (l > a || r < a) return;
		if (l == r) {
			mn[node] = min(mn[node], b);
			mx[node] = max(mx[node], b);
			return;
		}
		update(l, mid, a, b, tl); update(mid + 1, r, a, b, tr);
		pull(l, r, node);
	}
	int get_mx (int l, int r, int a, int b, int node) {
		if (l > b || r < a) return 0;
		if (l >= a && r <= b) return mx[node];
		return max(get_mx(l, mid, a, b, tl), get_mx(mid + 1, r, a, b, tr));
	}
	int get_mn (int l, int r, int a, int b, int node) {
		if (l > b || r < a) return MAXN;
		if (l >= a && r <= b) return mn[node];
		return min(get_mn(l, mid, a, b, tl), get_mn(mid + 1, r, a, b, tr));
	}
} dd[B];
pair <int, int> dp[B][MAXN];
int n, k, m;
pair <int, int> a[MAXN];
vector <pair <int, int>> sweep[MAXN];
void prep (int c) {
	dd[c].build(1, n, 1);
	for (int i = 1; i <= n; i++) {
		dd[c].update(1, n, i, dp[c][i].first, 1);
		dd[c].update(1, n, i, dp[c][i].second, 1);		
	}
}
pair <int, int> mm (pair <int, int> x, int c) {
	int l = dd[c].get_mn(1, n, x.first, x.second, 1);
	int r = dd[c].get_mx(1, n, x.first, x.second, 1);
	return {l, r};
}
void solve () {
	cin >> n >> k >> m;
	for (int i = 1; i <= n; i++) {
		dp[0][i] = {i, i};
	}	
	for (int i = 1; i <= m; i++) {
		cin >> a[i].first >> a[i].second;
	}
	for (int i = 1; i <= n; i++) {
		sweep[i].clear();
	}
	for (int i = 1; i <= m; i++) {
		if (a[i].first < a[i].second) {
			sweep[a[i].first].push_back({a[i].second, 1});
			sweep[min(a[i].first + k, a[i].second + 1)].push_back({a[i].second, -1});
		}
	}
	multiset <int> cur;
	for (int i = 1; i <= n; i++) {
		for (auto j : sweep[i]) {
			if (j.second == 1) {
				cur.insert(j.first);
			} else {
				cur.erase(cur.lower_bound(j.first));
			}
		}
		if (!cur.empty()) {
			dp[0][i].second = max(dp[0][i].second, *(--cur.end()));
		}
	}
	for (int i = 1; i <= n; i++) {
		sweep[i].clear();
	}
	for (int i = 1; i <= m; i++) {
		if (a[i].first > a[i].second) {
			sweep[a[i].first].push_back({a[i].second, 1});
			sweep[max(a[i].first - k, a[i].second - 1)].push_back({a[i].second, -1});
		}
	}
	cur.clear();
	for (int i = n; i >= 1; i--) {
		for (auto j : sweep[i]) {
			if (j.second == 1) {
				cur.insert(j.first);
			} else {
				cur.erase(cur.lower_bound(j.first));
			}
		}
		if (!cur.empty()) {
			dp[0][i].first = min(dp[0][i].first, *(cur.begin()));
		}
	}
	prep(0);
	for (int i = 1; i < B; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = mm(dp[i - 1][j], i - 1);
		}
		prep(i);
	}
	int q; cin >> q;
	while (q--) {
		int s, t; cin >> s >> t;
		pair <int, int> u = {s, s};
		int ans = 0;
		for (int i = B - 1; i >= 0; i--) {
			u = mm(u, i);
		}
		if (u.first > t || u.second < t) {
			cout << "-1\n";
			continue;
		}
		u = {s, s};
		for (int i = B - 1; i >= 0; i--) {
			auto g = mm(u, i);
			if (g.first > t || g.second < t) {
				ans += (1 << i);
				u = g;
			}
		}
		cout << ans + 1 << '\n';
	}
}		
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) 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