Submission #1007200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007200		THXuan	Railway Trip 2 (JOI22_ho_t4)	C++14	0 / 100	2074 ms	11604 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define INF 1e9
using namespace std;
typedef long long ll;
const ll maxn = 2e5 + 1;
int mn[4 * maxn], mx[4 * maxn];
pair<int, int>lazy[4 * maxn];

void build(int v, int l, int r) {
	if (l == r) {
		mx[v] = 0;
		mn[v] = INF;
		return;
	}
	int m = (l + r) / 2;
	build(2 * v, l, m);
	build(2 * v + 1, m + 1, r);
	mn[v] = min(mn[2 * v], mn[2 * v + 1]);
	mx[v] = max(mx[2 * v], mx[2 * v + 1]);
}

void pushdown(int v) {
	if (lazy[v].second) {
		lazy[2 * v].second = lazy[v].second;
		lazy[2 * v + 1].second = lazy[v].second;
		mx[2 * v] = max(mx[2 * v], lazy[v].second);
		mx[2 * v + 1] = max(mx[2 * v + 1], lazy[v].second);
		lazy[v].second = 0;
	}
	if (lazy[v].first) {
		lazy[2 * v].first = lazy[v].first;
		lazy[2 * v + 1].first = lazy[v].first;
		mn[2 * v] = min(mn[2 * v], lazy[v].first);
		mn[2 * v + 1] = min(mn[2 * v + 1], lazy[v].first);
		lazy[v].first = 0;
	}
}

void update(int v, int l, int r, int tl, int tr, int val, int type) {
	if (l > r)return;
	if (l == tl && r == tr) {
		if (type == 1) {
			lazy[v].second = max(lazy[v].second, val);
			mx[v] = max(mx[v], lazy[v].second);
		}
		else {
			if (!lazy[v].first) lazy[v].first = val;
			else lazy[v].first = min(lazy[v].first, val);
			mn[v] = min(mn[v], lazy[v].first);
		}
		return;
	}
	pushdown(v);
	int tm = (tl + tr) / 2;
	if (r <= tm) update(2 * v, l, r, tl, tm, val, type);
	else if (l >= tm + 1) update(2 * v + 1, l, r, tm + 1, tr, val, type);
	else {
		update(2 * v, l, tm, tl, tm, val, type);
		update(2 * v + 1, tm + 1, r, tm + 1, tr, val, type);
	}
	mx[v] = max(mx[2 * v], mx[2 * v + 1]);
	mn[v] = min(mn[2 * v], mn[2 * v + 1]);
}

pair<int, int>query(int v, int tl, int tr, int l, int r) {
	if (l > r)return { 0, 0 };
	if (l == tl && r == tr)return { mn[v], mx[v] };
	pushdown(v);
	int tm = (tl + tr) / 2;
	if (r <= tm)return query(2 * v, tl, tm, l, r);
	else if (l > tm)return query(2 * v + 1, tm + 1, tr, l, r);
	else {
		pair<int, int> left = query(2 * v, tl, tm, l, tm);
		pair<int, int> right = query(2 * v + 1, tm + 1, tr, tm + 1, r);
		return { min(left.first, right.first), max(left.second, right.second) };
	}
}

int lf(int l, int r, int t, int n) {
	if (!l) return -1;
	int ans = 1; int pl = 0, pr = 0;
	while (true) {
		if (t >= l && t <= r) return ans;
		if (pl == l && pr == r) { return -1; }
		pl = l; pr = r;
		int left = min(l, query(1, 1, n, l, r).first);
		int right = max(r, query(1, 1, n, l, r).second);
		if (left != 0) l = left;
		if (right != INF) r = right;
		++ans;
	}
}

int rg(int l, int r, int t, int n) {
	if (r == INF) return -1;
	int ans = 1; int pl = 0, pr = 0;
	while (true) {
		if (t >= l && t <= r) return ans;
		if (pl == l && pr == r) { return -1; }
		pl = l; pr = r;
		int left = min(l, query(1, 1, n, l, r).first);
		int right = max(r, query(1, 1, n, l, r).second);
		if (left != 0) l = left;
		if (right != INF) r = right;
		++ans;
	}
}

void solve()
{
	int n, k; cin >> n >> k;
	int m; cin >> m;
	build(1, 1, n);
	for (int i = 1; i <= m; i++) {
		int l, r; cin >> l >> r;
		if (l < r)update(1, l, min(l + k - 1, r - 1), 1, n, r, 1);
		else update(1, max(l - k + 1, r + 1), l, 1, n, r, 2);
	}
	/*for (int i = 1; i <= n; i++) {
		cout << query(1, 1, n, i, i).first << " " << query(1, 1, n, i, i).second << "\n";
	}*/
	int q; cin >> q;
	while (q--) {
		int s, t; cin >> s >> t;// from -> to
		int l = 0, r = 0;
		// check the left train
		l = query(1, 1, n, s, s).first; r = s;
		int ans1 = lf(l, r, t, n);
		// check the right train
		l = s; r = query(1, 1, n, s, s).second;
		int ans2 = rg(l, r, t, n);
		if (ans1 != -1 && ans2 != -1)cout << min(ans1, ans2) << '\n';
		else if (ans1 == -1 && ans2 != -1) cout << ans2 << "\n";
		else if (ans1 != -1 && ans2 == -1)cout << ans1 << '\n';
		else cout << -1 << "\n";
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;// cin>>t;
	while (t--) solve();
	return 0;
}

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