#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vec vector
const int MXN = 200'005;
const int LOG = 20;
const int INF = 1e9;
int32_t main() {
int N, M;
cin >> N >> M;
vec<pair<int, int>> rs(N);
for(int i = 0; i<N; i++) {
cin >> rs[i].first >> rs[i].second;
if(rs[i].second < rs[i].first) rs[i].second += M;
}
sort(rs.begin(), rs.end());
set<pair<int, int>> rightmost;
vec<vec<pair<int, int>>> binjmps(N, vec<pair<int, int>>(LOG));
for(int i = 0; i<N; i++) {
rs.push_back({rs[i].first+M, rs[i].second+M});
}
int j = 0;
for(int i = 0; i<N; i++) {
while(rs[j].first <= rs[i].second) {
rightmost.insert({rs[j].second, j});
j++;
}
pair<int, int> r = *rightmost.rbegin();
assert(r.first >= rs[i].second);
binjmps[i][0] = {r.first-rs[i].second, r.second%N};
//cerr << r.second%N << ' ';
rightmost.erase({rs[i].second, i});
}
//cerr << '\n';
int mxlog = LOG;
for(int i = 1; i<LOG && i<mxlog; i++) {
for(int j = 0; j<N; j++) {
int k = binjmps[j][i-1].second;
binjmps[j][i].first = binjmps[j][i-1].first+binjmps[k][i-1].first;
binjmps[j][i].second = k;
if(binjmps[j][i].first > M) {
mxlog = i+1;
}
}
}
int ans = INF;
for(int i = 0; i<N; i++) {
int d = rs[i].second-rs[i].first;
int cur = i;
int res = 0;
for(int j = mxlog-1; j>=0; j--) {
int nd = binjmps[cur][j].first + d;
if(nd < M) {
d = nd;
cur = binjmps[cur][j].second;
res += (1<<j);
}
}
res += 1;
d += binjmps[cur][0].first;
if(d >= M) {
ans = min(ans, res+1);
}
}
if(ans == INF) cout << -1 << '\n';
else {
cout << ans << '\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
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 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
432 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
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 |
- |
