#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
signed main() {
int n, m; cin >> n >> m; vector<pair<int,int>> v(n);
for(int i=0;i<n;i++) {cin >> v[i].f >> v[i].s; if(v[i].s < v[i].f) v[i].s += m;} sort(begin(v),end(v));
for(int i=0;i<n;i++) v.push_back({v[i].f+m,v[i].s+m}); for(int i=0;i<n;i++) v.push_back({v[i].f+2*m,v[i].s+2*m});
int ans = 1e9; vector<pair<int,int>> t(3*n); vector<vector<pair<int,int>>> c(n,vector<pair<int,int>>(20));
t[0] = {v[0].s,0}; for(int i=1;i<3*n;i++) if(t[i-1].f < v[i].s) t[i].f = v[i].s, t[i].s = i%n; else t[i] = t[i-1];
for(int i=0;i<n;i++) {
auto p = t[upper_bound(v.begin(),v.end(),make_pair(v[i+n].s,(int)1e18))-begin(v)-1];
if(p.f <= v[i+n].s) {cout << -1; return 0;}
else c[i][0].f = p.s, c[i][0].s = (v[p.s].s-v[i].s+m)%m;
}
for(int i=1;i<20;i++) for(int j=0;j<n;j++) c[j][i].f = c[c[j][i-1].f][i-1].f, c[j][i].s = c[j][i-1].s+c[c[j][i-1].f][i-1].s;
for(int i=0;i<n;i++) {
int a = 1, b = i, d = v[i].s-v[i].f;
for(int j=19;j+1;j--) if(c[b][j].s+d < m) a += (1<<j), d += c[b][j].s, b = c[b][j].f;
ans = min(ans, a+1);
}
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |