#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
int s, e, m, v, lz;
node *l, *r;
node(int _s, int _e) {
s = _s, e = _e, m = (s+e)/2, v = 0, lz = -1;
if(s != e) {
l = new node(s, m);
r = new node(m+1, e);
}
}
void prop() {
if(lz == -1) return;
v = lz;
if(s != e) {
l->lz = lz;
r->lz = lz;
}
lz = -1;
}
void update(int x, int y, int val) {
prop();
if(x <= s && e <= y) {lz = val; return;}
else if(x > m) r->update(x, y, val);
else if(y <= m) l->update(x, y, val);
else l->update(x, y, val), r->update(x, y, val);
l->prop(); r->prop();
v = max(l->v, r->v);
}
int get(int x) {
prop();
if(s == e) return v;
else if(x > m) return r->get(x);
else return l->get(x);
}
} *root;
vector<int> adj[200000];
int p[200000][18], depth[200000];
void dfs(int x, int pa, int d) {
depth[x] = d;
p[x][0] = pa;
for(int i = 1; i < 18; i++) {
if(p[x][i-1] == -1) break;
p[x][i] = p[p[x][i-1]][i-1];
}
for(int i : adj[x]) dfs(i, x, d+1);
}
int getp(int x, int k) {
for(int i = 0; i < 18; i++) {
if(k&(1<<i)) x = p[x][i];
}
return x;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m, x, y;
cin >> n >> m;
pair<int, int> a[n];
vector<int> dis, act;
for(int i = 0; i < n; i++) {
cin >> x >> y;
if(y < x) y = y+m;
a[i] = {y, x};
dis.push_back(x);
dis.push_back(y);
}
sort(dis.begin(), dis.end());
dis.erase(unique(dis.begin(), dis.end()), dis.end());
for(int i : dis) act.push_back(i);
for(int i = 0; i < n; i++) {
a[i].first = lower_bound(dis.begin(), dis.end(), a[i].first)-dis.begin();
a[i].second = lower_bound(dis.begin(), dis.end(), a[i].second)-dis.begin();
}
sort(a, a+n);
root = new node(0, dis.size());
for(int i = 0; i < n; i++) {
root->update(a[i].second, a[i].first, a[i].first);
}
for(int i = 0; i < dis.size(); i++) {
if(root->get(i) != i) adj[root->get(i)].push_back(i);
}
memset(p, -1, sizeof(p));
dfs(dis.size()-1, -1, 0);
for(int i = 0; i < dis.size()-2; i++) if(p[i][0] == -1) {
cout << -1 << '\n';
return 0;
}
int l = 0, r = n, md;
while(l < r) {
md = (l+r)/2;
bool ok = false;
for(int i = 0; i < dis.size()-1; i++) {
if(act[getp(i, min(md, depth[i]))]-act[i] >= m) ok = true;
}
if(ok) r = md;
else l = md+1;
}
cout << l << '\n';
}
Compilation message
Main.cpp: In function 'int32_t main()':
Main.cpp:87:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int i = 0; i < dis.size(); i++) {
| ~~^~~~~~~~~~~~
Main.cpp:92:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int i = 0; i < dis.size()-2; i++) if(p[i][0] == -1) {
| ~~^~~~~~~~~~~~~~
Main.cpp:100:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(int i = 0; i < dis.size()-1; i++) {
| ~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
34640 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
34640 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
34640 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
34640 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
34640 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
34640 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
34640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
34640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
34640 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
34640 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
