| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1086454 |
2024-09-10T17:20:16 Z |
IBory |
Fire (BOI24_fire) |
C++17 |
|
1 ms |
4444 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;
}
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;
for (int n = 18; n >= 0; --n) {
auto [a, b] = ST[R[n][cur]];
if (b < goal) cur = R[n][cur];
}
cur = R[0][cur];
if (goal <= ST[cur].second) ans = min(ans, cur - i + 1);
}
cout << (ans == 1e9 ? -1 : ans);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
