#include <bits/stdc++.h>
#define el '\n'
#define FNAME "NAME"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9+7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}
void setup(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
if (fopen(FNAME".inp","r")){
freopen(FNAME".inp","r",stdin);
freopen(FNAME".out","w",stdout);
}
}
const int MAXN = 4e5 + 5;
const int LOG = 20;
const int INF = 1e9 + 15092007;
int n;
long long m;
long long s[MAXN],e[MAXN];
int nxt[MAXN];
int up[LOG+1][MAXN];
void init(){
cin>>n>>m;
for (int i=0;i<n;i++) cin>>s[i]>>e[i];
}
void removeUseless(){
vector<pair<long long,long long>> shift;
for (int i=0;i<n;i++){
shift.emplace_back(s[i],e[i]);
}
sort(allof(shift),[](const pair<long long,long long> &a,const pair<long long,long long> &b){
return (a.first<b.first or (a.first==b.first and a.second>b.second));
});
int newN=0;
long long maxE=-1;
for (pair<long long,long long> p : shift){
long long start,end; tie(start,end) = p;
if (maximize(maxE,end)){
s[newN] = start;
e[newN] = end;
newN++;
}
}
n = newN;
}
void modify(){
// ! raise overnight intervals
for (int i=0;i<n;i++) if (s[i] > e[i]) e[i] += m;
// ! duplicate
for (int i=0;i<n;i++){
s[i+n] = s[i] + m;
e[i+n] = e[i] + m;
}
n*=2;
removeUseless();
}
void calNext(){
vector<pair<long long,int>> shift;
for (int i=0;i<n;i++){
shift.emplace_back(s[i],i);
}
sort(allof(shift));
int r=0;
for (pair<long long,int> p : shift){
int ID = p.second;
while (r<n){
int nxtID = shift[r].second;
if (s[nxtID] > e[ID]) break;
r++;
}
nxt[ID] = shift[r-1].second;
}
}
void calUp(){
for (int i=0;i<n;i++){
up[0][i] = nxt[i];
}
for (int k=1;k<=LOG;k++){
for (int i=0;i<n;i++){
up[k][i] = up[k-1][up[k-1][i]];
}
}
}
int getVal(int firstShift){
long long startT = s[firstShift];
int cnt=1;
int u=firstShift;
for (int k=LOG;k>=0;k--){
if (e[up[k][u]] < (startT + m)){
cnt += (1<<k);
u = up[k][u];
}
}
cnt++;
u = up[0][u];
if (e[u] < (startT + m)) return INF;
return cnt;
}
void sol(){
modify();
calNext();
calUp();
int res = INF;
for (int i=0;i<n;i++){
minimize(res,getVal(i));
}
cout<< (res==INF ? -1 : res);
}
int main(){
setup();
init();
sol();
}
Compilation message (stderr)
Main.cpp: In function 'void setup()':
Main.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | freopen(FNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | freopen(FNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |