#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, *root2;
vector<int> adj[800000];
int p[800000][20], depth[800000];
bool v[800000];
void dfs(int x, int pa, int d) {
v[x] = 1;
depth[x] = d;
p[x][0] = pa;
for(int i = 1; i < 20; i++) {
if(p[x][i-1] == -1) break;
p[x][i] = p[p[x][i-1]][i-1];
}
for(int i : adj[x]) if(!v[i]) dfs(i, x, d+1);
}
int getp(int x, int k) {
for(int i = 0; i < 20; 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;
n *= 2;
pair<int, int> a[n];
vector<int> dis, dis2, act;
for(int i = 0; i < n; i++) {
if(i < n/2) {
cin >> x >> y;
if(y < x) y = y+m;
a[i] = {y, x};
dis.push_back(x);
dis.push_back(y);
} else {
a[i].first = a[i-n/2].first+m;
a[i].second = a[i-n/2].second+m;
dis.push_back(a[i].first);
dis.push_back(a[i].second);
}
}
sort(dis.begin(), dis.end());
dis.erase(unique(dis.begin(), dis.end()), dis.end());
for(int i : dis) act.push_back(i);
root = new node(0, dis.size());
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);
for(int i = 0; i < n; i++) {
root->update(a[i].second, a[i].first, a[i].first);
}
int par[dis.size()];
for(int i = 0; i < dis.size(); i++) {
if(root->get(i) != i) adj[root->get(i)].push_back(i);
par[i] = root->get(i);
}
int cur = 0;
bool ok = false;
while(cur < dis.size()-1) {
while(par[cur] != cur) {
cur = par[cur];
}
if(act[cur]-act[0] >= m) ok = true;
cur++;
}
if(!ok) {
cout << -1 << '\n';
return 0;
}
memset(p, -1, sizeof(p));
for(int i = dis.size()-1; i >= 0; i--) if(!v[i]) {
dfs(i, -1, 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:100: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]
100 | for(int i = 0; i < dis.size(); i++) {
| ~~^~~~~~~~~~~~
Main.cpp:107:12: 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]
107 | while(cur < dis.size()-1) {
| ~~~~^~~~~~~~~~~~~~
Main.cpp:126: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]
126 | for(int i = 0; i < dis.size()-1; i++) {
| ~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
147024 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
147020 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
147024 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
147020 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
147024 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
147020 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
21 ms |
147024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
22 ms |
147016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
147024 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
147020 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
