제출 #1086072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1086072		ymm	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	369 ms	36504 KiB

Main

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

template<class Cmp>
struct Obj {
	vector<int> seg;
	int sz;

	int ko(int x, int y) {
		return Cmp()(x, y)? x: y;
	}

	void init(int n) {
		seg.assign(2*n, 0);
		sz = n;
	}

	int &operator[](int i) {
		return seg[i + sz];
	}

	void build() {
		LoopR (i,0,sz)
			seg[i] = ko(seg[2*i], seg[2*i+1]);
	}

	int get(int l, int r) {
		l += sz; r += sz;
		int ans = seg[l];
		while (l < r) {
			if (l&1) ans = ko(ans, seg[l++]);
			if (r&1) ans = ko(ans, seg[--r]);
			l /= 2;
			r /= 2;
		}
		return ans;
	}
};

const int lg = 20;
Obj<less<int>> p_lf, lf[lg];
Obj<greater<int>> p_ri, ri[lg];
int n, K;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int m;
	cin >> n >> K >> m;
	p_lf.init(n);
	p_ri.init(n);
	Loop (i,0,n)
		p_lf[i] = p_ri[i] = i;
	while (m--) {
		int i, j;
		cin >> i >> j;
		--i; --j;
		if (i < j)
			p_ri[i] = max(p_ri[i], j);
		if (i > j)
			p_lf[i] = min(p_lf[i], j);
	}
	p_ri.build();
	p_lf.build();
	lf[0].init(n);
	ri[0].init(n);
	Loop (i,0,n) {
		lf[0][i] = p_lf.get(i, min<int>(n, i + K));
		ri[0][i] = p_ri.get(max<int>(0, i - K + 1), i + 1);
	}
	lf[0].build();
	ri[0].build();
	Loop (i,0,lg-1) {
		lf[i+1].init(n);
		ri[i+1].init(n);
		Loop (j,0,n) {
			int l = lf[i][j];
			int r = ri[i][j];
			lf[i+1][j] = lf[i].get(l, r+1);
			ri[i+1][j] = ri[i].get(l, r+1);
		}
		lf[i+1].build();
		ri[i+1].build();
	}
	int q;
	cin >> q;
	while (q--) {
		int s, t;
		cin >> s >> t;
		--s; --t;
		int l = s, r = s;
		int ans = 0;
		LoopR (i,0,lg) {
			int l2 = lf[i].get(l, r+1);
			int r2 = ri[i].get(l, r+1);
			if (t < l2 || r2 < t) {
				if (i == lg-1) {
					ans = -2;
					break;
				}
				l = l2;
				r = r2;
				ans += 1<<i;
			}
		}
		cout << ans + 1 << '\n';
	}
}

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