Submission #530319

#	Time	Username	Problem	Language	Result	Execution time	Memory
530319		yungyao	Railway Trip 2 (JOI22_ho_t4)	C++17	52 / 100	2080 ms	14080 KiB

Main

using namespace std;
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>

typedef long long LL;
typedef pair<int,int> pii;
#define pb push_back
#define mkp make_pair
#define F first
#define S second
#define iter(x) x.begin(),x.end()
#define REP(n) for (int __=n;__--;)
#define REP0(i,n) for (int i=0;i<n;++i)
#define REP1(i,n) for (int i=1;i<=n;++i)

const int maxn = 1e5+10, mod = 0;
const LL inf = 0;

int mx[maxn], mn[maxn];
struct segmenttree{
	int val[maxn*4], type;

	int pull(int l, int r){
		return type == 1 ? max(l, r) : min(l, r);
	}
	void maketree(int cur, int LB, int RB){
		if (LB == RB){
			if (type == 1) val[cur] = mx[LB];
			else val[cur] = mn[LB];
		}
		else{
			int m = (LB + RB) / 2;
			maketree(cur*2, LB, m);
			maketree(cur*2+1, m+1, RB);
			val[cur] = pull(val[cur*2], val[cur*2+1]);
		}
	}
	void init(int n, int _type){
		type = _type;
		maketree(1, 1 ,n);
	}
	int query(int l, int r, int cur, int LB, int RB){
		if (l == LB and r == RB) return val[cur];
		int m = (LB + RB) / 2;
		if (r <= m) return query(l, r, cur*2, LB, m);
		else if (l > m) return query(l, r, cur*2+1, m+1, RB);
		else return pull(query(l, m, cur*2, LB, m), query(m+1, r, cur*2+1, m+1, RB));
	}
}seg[2];

void solve2(int n, int m){
	vector <int> mx[17], mn[17];
	REP0(i, 17){mx[i].resize(n+1); mn[i].resize(n+1);}
	REP1(i, n){mx[0][i] = i; mn[0][i] = i;}
	REP(m){
		int a, b;

		cin >> a >> b;
		mx[0][a] = max(mx[0][a], b);
		mn[0][a] = min(mn[0][a], b);
	}
	REP1(i, n) mx[0][i] = max(mx[0][i], mx[0][i-1]);
	for (int i=n-1;i;--i) mn[0][i] = min(mn[0][i], mn[0][i+1]);
	REP1(i, 16) REP1(j, n){
		mx[i][j] = mx[i-1][mx[i-1][j]];
		mn[i][j] = mn[i-1][mn[i-1][j]];
	}
	int q;

	cin >> q;
	REP(q){
		int s, t;

		cin >> s >> t;
		int ans = 0;
		if (s < t){
			for (int i=16;i>=0;--i){
				if (mx[i][s] < t){
					s = mx[i][s];
					ans |= 1 << i;
				}
			}
			if (mx[0][s] < t) ans = -1;
			else ++ans;
		}
		else{
			for (int i=16;i>=0;--i){
				if (mn[i][s] > t){
					s = mn[i][s];
					ans |= 1 << i;
				}
			}
			if (mn[0][s] > t) ans = -1;
			else ++ans;
		}
		cout << ans << '\n';
	}
}

void solve(){
	int n, k, m, q;

	cin >> n >> k >> m;
	if (k == n-1){
		solve2(n, m);
		return;
	}
	REP1(i, n) mn[i] = mx[i] = i;
	REP(m){
		int a, b;

		cin >> a >> b;
		mx[a] = max(mx[a], b);
		mn[a] = min(mn[a], b);
	}
	deque <pii> dq;
	REP1(i, n){
		while (!dq.empty() and mx[i] >= dq.back().F) dq.pop_back();
		dq.push_back(mkp(mx[i], i));
		if (dq.front().S + k <= i) dq.pop_front();
		mx[i] = dq.front().F;
	}
	while (!dq.empty()) dq.pop_back();
	for (int i=n;i;--i){
		while (!dq.empty() and mn[i] <= dq.back().F) dq.pop_back();
		dq.push_back(mkp(mn[i], i));
		if (dq.front().S - k >= i) dq.pop_front();
		mn[i] = dq.front().F;
	}
	seg[0].init(n, 1);
	seg[1].init(n, 2);
	cin >> q;
	REP(q){
		int s, t;

		cin >> s >> t;
		pii r = mkp(s, s);
		int cnt = 0;
		while (t < r.F or t > r.S){
			++cnt;
			pii nr = mkp(seg[1].query(r.F, r.S, 1, 1, n), seg[0].query(r.F, r.S, 1, 1, n));
			if (r == nr){
				cnt = -1;
				break;
			}
			r = nr;
		}
		cout << cnt << '\n';
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	solve();

	return 0;
}

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