#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;
vec<int> dp(N*2, INF);
for(int i = 0; i<N; i++) {
if(rs[i].first == 0) dp[i] = 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);
dp[r.second] = min(dp[r.second], dp[i]+1);
binjmps[i][0] = {r.first-rs[i].second, r.second%N};
//cerr << r.second%N << ' ';
rightmost.erase({rs[i].second, i});
}
int ans = INF;
for(int i = 0; i<N*2; i++) {
if(rs[i].second >= M) {
ans = min(dp[i], ans);
}
}
cout << ans << '\n';
return;
//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;
}
}
}
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';
}
}
Compilation message
Main.cpp: In function 'int32_t main()':
Main.cpp:55:2: error: return-statement with no value, in function returning 'int32_t' {aka 'int'} [-fpermissive]
55 | return;
| ^~~~~~
