Submission #529477

#	Time	Username	Problem	Language	Result	Execution time	Memory
529477		fhvirus	Railway Trip 2 (JOI22_ho_t4)	C++17	0 / 100	302 ms	24792 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll; typedef pair<int, int> pii;
#define pb emplace_back
#define AI(x) begin(x),end(x)
#define ff first
#define ss second
#ifdef OWO
#define debug(args...) LKJ("\033[0;32m[ " + string(#args) + " ]\033[0m", args)
template<class I> void LKJ(I&&x) { cerr << x << endl; }
template<class I, class...T> void LKJ(I&&x, T&&...t) { cerr << x << ", "; LKJ(t...); }
template<class I> void OI(I a, I b) { while (a != b) cerr << *a << ' ', ++a; cerr << endl; }
#else
#define debug(...) 0
#define OI(...) 0
#endif

struct RMQ {
	int n; vector<int> val;
	RMQ() = default;
	void build(const vector<int>& v) {
		n = v.size();
		val.resize(n * 2);
		for (int i = 0; i < n; ++i)
			val[i + n] = v[i];
		for (int i = n - 1; i > 0; --i)
			val[i] = max(val[i << 1], val[i << 1 | 1]);
	}
	int query(int l, int r) {
		++r;
		int res = 0;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (l & 1) res = max(res, val[l++]);
			if (r & 1) res = max(res, val[--r]);
		}
		return res;
	}
};

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N, K; cin >> N >> K;
	int M; cin >> M;
	vector<int> A(M + 1), B(M + 1);
	for (int i = 1; i <= M; ++i)
		cin >> A[i] >> B[i];
	int Q; cin >> Q;
	vector<int> S(Q + 1), T(Q + 1);
	for (int i = 1; i <= Q; ++i)
		cin >> S[i] >> T[i];

	vector<vector<int>> ono(N + 1);
	for (int i = 1; i <= M; ++i) {
		assert(A[i] < B[i]);
		ono[A[i]].pb(B[i]);
		if (A[i] + K <= N)
			ono[A[i] + K].pb(-B[i]); 
	}

	multiset<int> st;
	vector<int> rightmost(N + 1, 0);
	for (int i = 1; i <= N; ++i) {
		for (const int& v: ono[i]) {
			if (v > 0) st.insert(v);
			else st.erase(-v);
		}
		if (!st.empty())
			rightmost[i] = max(i, *rbegin(st));
		else
			rightmost[i] = i;
	}

	int lg = __lg(N) + 1;
	RMQ rmq;
	vector<vector<int>> jmp(lg + 1, vector<int>(N + 1, 0));
	jmp[0] = rightmost;
	for (int l = 1; l <= lg; ++l) {
		rmq.build(jmp[l - 1]);
		for (int i = 1; i <= N; ++i) {
			int rb = jmp[l - 1][i];
			jmp[l][i] = rmq.query(i, rb);
		}
		debug(l);
		OI(AI(jmp[l]));
	}

	for (int i = 1; i <= Q; ++i) {
		int s = S[i], t = T[i];
		if (jmp[lg][s] < t) {
			cout << -1 << '\n';
			continue;
		}
		int ans = 0;
		for (int l = lg; l >= 0; --l)
			if (jmp[l][s] < t) {
				ans += (1 << l);
				s = jmp[l][s];
			}
		cout << ans + 1 << '\n';
	}

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
Main.cpp:84:3: note: in expansion of macro 'debug'
   84 |   debug(l);
      |   ^~~~~
Main.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define OI(...) 0
      |                 ^
Main.cpp:85:3: note: in expansion of macro 'OI'
   85 |   OI(AI(jmp[l]));
      |   ^~

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