Submission #1006138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006138		THXuan	Railway Trip 2 (JOI22_ho_t4)	C++14	0 / 100	2066 ms	11452 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] = l; 
		mn[v] = l;
		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) };
	}
}

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 = query(1, 1, n, s, s).first; int r = query(1, 1, n, s, s).second;
		int ans = 1;
		int pl = 0; int pr = 0;
		while (true) {
			if (t >= l && t <= r) break;
			if (pl == l && pr == r) { ans = -1; break; }
			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);
			l = left; r = right; ++ans;
		}
		cout << ans << "\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