제출 #1283484

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283484		third	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	698 ms	60432 KiB

Main

#include<bits/stdc++.h>
typedef int ll;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 100005
#define LOG 17
using namespace std;

// da xem goi y

const ll inf = 1e9;

bool ghuy4g;

ll n, k, m, q;

pii p[N][LOG + 2];

vector<pii> vt1, vt2;

bool cmp(pii a, pii b) {
	return a.fi > b.fi;
}

pii st[LOG + 2][4 * N];

pii cb(pii a, pii b) {
	return {min(a.fi, b.fi), max(a.se, b.se)};
}

void build(ll tt, ll id, ll l, ll r) {
	if (l == r) {
		st[tt][id] = p[l][tt];
		return;
	}
	ll mid = (l + r) / 2;
	build(tt, id * 2, l, mid);
	build(tt, id * 2 + 1, mid + 1, r);
	st[tt][id] = cb(st[tt][id * 2], st[tt][id * 2 + 1]);
}

pii get(ll tt, ll id, ll l, ll r, ll L, ll R) {
	if (l > R || r < L) return {inf, -inf};
	if (L <= l && r <= R) {
		return st[tt][id];
	}
	ll mid = (l + r) / 2;
	return cb(get(tt, id * 2, l, mid, L, R), get(tt, id * 2 + 1, mid + 1, r, L, R));
}

void pre2() {
	for (int j = 1; j <= LOG; j ++) {
		build(j - 1, 1, 1, n);
		for (int i = 1; i <= n; i ++) {
			pii prev = p[i][j - 1];
			pii nxt = get(j - 1, 1, 1, n, prev.fi, prev.se);
			p[i][j] = nxt;
		}
	}
	build(LOG, 1, 1, n);
}

void pre() {
	sort(vt1.begin(), vt1.end());
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	ll cur = 0;
	multiset<pii> s;
	for (int i = 1; i <= n; i ++) {
		while (cur < vt1.size() && vt1[cur].fi <= i) {
			s.insert({vt1[cur].se, cur});
			pq.push({min(vt1[cur].fi + k - 1, vt1[cur].se - 1), cur});
			cur ++ ;
		}
		while (pq.size() && pq.top().fi < i) {
			ll id = pq.top().se;
			pq.pop();
			s.erase(s.find({vt1[id].se, id}));
		}
		if (s.size()) {
			p[i][0].se = (*s.rbegin()).fi;
		}
		else {
			p[i][0].se = i;
		}
	}
	sort(vt2.begin(), vt2.end(), cmp);
	/*for (auto it : vt2) {
		cout << "vt2 " << it.fi << " " << it.se << endl;
	}*/
	cur = 0;
	s.clear();
	priority_queue<pii> pq2;
	for (int i = n; i >= 1; i --) {
		while (cur < vt2.size() && vt2[cur].fi >= i) {
			s.insert({vt2[cur].se, cur});
			pq2.push({max(vt2[cur].fi - k + 1, vt2[cur].se + 1), cur});
			cur ++ ;
		}
		while (pq2.size() && pq2.top().fi > i) {
			ll id = pq2.top().se;
			pq2.pop();
			s.erase(s.find({vt2[id].se, id}));
		}
		if (s.size()) {
			p[i][0].fi = (*s.begin()).fi;
		}
		else {
			p[i][0].fi = i;
		}
	}
	pre2();
}

pii kth_par(ll u, ll k) {
	pii cur = {u, u};
	for (int j = LOG; j >= 0; j --) {
		if (k >= (1 << j)) {
			k -= (1 << j);
			cur = cb(cur, get(j, 1, 1, n, cur.fi, cur.se));
		}
	}
	return cur;
}

void solve() {
	//in();
	cin >> q;
	for (int i = 1; i <= q; i ++) {
		ll u, v;
		cin >> u >> v;
		if (u == v) {
			cout << 0 << endl;
			continue;
		}
		pii xet = kth_par(u, n);
		if (!(xet.fi <= v && v <= xet.se)) {
			cout << -1 << endl;
			continue;
		}
		pii cur = {u, u};
		ll res = 0;
		for (int j = LOG; j >= 0; j --) {
			xet = get(j, 1, 1, n, cur.fi, cur.se);
			pii nxt = cb(xet, cur);
			if (nxt.fi <= v && v <= nxt.se) {
				
			}
			else {
				cur = xet;
				res += (1 << j);
			}
		}
		cur = cb(cur, get(0, 1, 1, n, cur.fi, cur.se));
		res ++ ;
		cout << res << endl;
	}	
}

bool klinh;

signed main() {
   // freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	//srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
   	cin >> n >> k;
   	cin >> m;
   	for (int i = 1; i <= m; i ++) {
   		ll u, v;
   		cin >> u >> v;
   		if (u < v) {
   			vt1.push_back({u, v});
   		}
   		else {
   			vt2.push_back({u, v});
   		}
   	}
   	
   	pre();
   	solve();
   	
   	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

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