oj.uz

Submission #1086460

# Submission time Handle Problem Language Result Execution time Memory
1086460 2024-09-10T17:25:05 Z IBory Fire (BOI24_fire) C++17
0 / 100
 0 ms 468 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 400007;
int R[19][MAX];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M;
	cin >> N >> M;
	vector<pii> T, ST;
	for (int i = 1; i <= N; ++i) {
		int a, b;
		cin >> a >> b;
		if (b < a) b += M;
		T.emplace_back(a, b);
		T.emplace_back(a + M, b + M);
	}

	sort(T.begin(), T.end());
	for (auto [a, b] : T) {
		while (!ST.empty() && ST.back().first == a && ST.back().second <= b) ST.pop_back();
		if (ST.empty() || ST.back().second < b) ST.emplace_back(a, b);
	}

	N = ST.size();
	for (int i = 0; i < N; ++i) {
		auto [a, b] = ST[i];
		auto it = lower_bound(ST.begin(), ST.end(), pii{b, (int)2e9}) - ST.begin();
		R[0][i] = it - 1;

		assert(ST[R[0][i]].first <= b);
		if (i) {
			auto [c, d] = ST[i - 1];
			assert(c < a && d < b);
		}
	}
	for (int n = 1; n < 19; ++n) for (int i = 0; i < N; ++i) R[n][i] = R[n - 1][R[n - 1][i]];

	int ans = 1e9;
	for (int i = 0; i < N; ++i) {
		int cur = i, goal = ST[cur].first + M, go = 1;
		for (int n = 18; n >= 0; --n) {
			auto [a, b] = ST[R[n][cur]];
			if (b < goal) {
				cur = R[n][cur];
				go += 1 << n;
			}
		}
		cur = R[0][cur];
		if (goal <= ST[cur].second) ans = min(ans, go + 1);
	}

	cout << (ans == 1e9 ? -1 : ans);
	return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -