제출 #1263901

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263901		goulthen	Railway Trip 2 (JOI22_ho_t4)	C++20	25 / 100	115 ms	52424 KiB

Main

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

#define int long long
#define rep(i,a,b) for (int i = a; i <= b; ++i)
#define per(i,a,b) for (int i = a; i >= b; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define pb push_back

const int MAXN = 1e5 + 10;
vector<pii> g[2];
int p[MAXN][31][2];

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(nullptr);

	int n,m,k,q; cin >> n >> k >> m;
	rep(i,1,m) {
		int u,v;cin >> u >> v;
		g[(u>=v)].pb({u,v});
	}
	cin >> q;

	sort(all(g[0]));
	int ptr=0, mx = -1;
	rep(i,1,n) {
		while (ptr < g[0].size() && g[0][ptr].fi == i) {
			mx = max(mx, g[0][ptr++].se);
		}

		p[i][0][0] = (mx<i?i:mx);
	}
	sort(all(g[1]), greater<pii>());
	ptr = 0;
	int mn = n;
	per(i,n,1) {
		while (ptr < g[1].size() && g[1][ptr].fi == i) {
			mn = min(mn, g[1][ptr++].se);
		}
		p[i][0][1] = (mn>i?i:mn);
	}

	rep(k,0,1) {
		rep(j,1,30) {
			rep(i,1,n) {
				p[i][j][k] = p[p[i][j-1][k]][j-1][k];
			}
		}
	}
	while (q--) {
		int s,t;cin >> s >> t;
		int ans = 0, ptr = s;

		if (s <= t) {
			per(k,30,0) {

				if(p[ptr][k][0] < t) {
					ptr = p[ptr][k][0];
					ans+=(1<<k);
				}
			}
			ptr = p[ptr][0][0];
			cout << (ptr>=t ? ans+1 : -1) << '\n';


		} else {
			per(k,30,0) {
				if(p[ptr][k][1] > t) {
					ptr = p[ptr][k][1];
					ans+=(1<<k);
				}
			}
			ptr = p[ptr][0][1];
			cout << (ptr<=t ? ans+1 : -1) << '\n';
		}

	}

}

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