#include <bits/stdc++.h>
using namespace std;
const int maxn = 250005, maxN = 1e6 + 5, INF = 4e9 + 10;
int n, k;
pair<int,int> a[maxn];
int sz;
vector<int> vals = {-INF};
int ldc(int x) {return lower_bound(vals.begin(), vals.end(), x) - vals.begin();}
int rdc(int x) {return upper_bound(vals.begin(), vals.end(), x) - vals.begin() - 1;}
struct node {
int lpt, rpt, val;
};
struct thing {
int id, dist, cnt;
bool operator < (const thing &b) const {
return dist > b.dist;
}
};
pair<int,int> b[maxn];
node seg[18000000];
int pt = 1;
vector<int> lg = {1};
void build(int id, int l, int r) {
seg[id] = {0, 0, 0};
if (l==r) return;
int mid = (l+r) >> 1;
seg[id].lpt = pt++;
build(pt, l, mid);
seg[id].rpt = pt++;
build(pt, mid+1, r);
}
void update(int id, int l, int r, int target) {
seg[id].val++;
if (l==r) return;
int mid = (l+r)/2;
pt++;
if (target<=mid) {
seg[pt] = seg[seg[id].lpt];
seg[id].lpt = pt;
update(pt, l, mid, target);
} else {
seg[pt] = seg[seg[id].rpt];
seg[id].rpt = pt;
update(pt, mid+1, r, target);
}
}
int qry(int id, int l, int r, int findl, int findr) {
if (r<findl || findr<l) return 0;
if (findl<=l && r<=findr) return seg[id].val;
int mid = (l+r) >> 1;
int lhs = qry(seg[id].lpt, l, mid, findl, findr);
int rhs = qry(seg[id].rpt, mid+1, r, findl, findr);
return lhs + rhs;
}
int cunt(int id, int dist) {
int L = ldc(a[id].second - dist), R = rdc(a[id].second + dist);
int val = qry(lg[id], 1, sz, L, R);
int x = lower_bound(a+1, a+n+1, make_pair(a[id].first - dist, -INF)) - a - 1;
val -= qry(lg[x], 1, sz, L, R);
return val;
}
priority_queue<thing> pq;
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
for (int i=1;i<=n;i++) {
int x, y;
cin >> x >> y;
a[i] = {x+y, x-y};
vals.push_back(x-y);
}
sort(a+1, a+n+1);
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
sz = vals.size() - 1;
build(1, 1, sz);
for (int i=1;i<=n;i++) {
pt++;
seg[pt] = seg[lg.back()];
lg.push_back(pt);
update(pt, 1, sz, ldc(a[i].second));
}
for (int i=2;i<=n;i++) {
b[i] = {0, 1};
int l = 1, r = INF;
while (l < r) {
int mid = (l+r)/2;
if (cunt(i, mid) == b[i].second) l = mid+1;
else r = mid;
}
int x = cunt(i, l);
pq.push({i, l, x});
// cout << i << " " << l << " " << cunt(i, l) << endl;
}
int total = 0;
while (true) {
int id = pq.top().id, dist = pq.top().dist, cnt = pq.top().cnt;
pq.pop();
// cout << id << " " << dist << " " << cnt << endl;
for (;b[id].second<cnt;b[id].second++) {
cout << dist << '\n';
total++;
if (total == k) return 0;
}
if (b[id].second == id) continue;
b[id].first = dist;
int l = dist+1, r = INF;
while (l < r) {
int mid = (l+r)/2;
if (cunt(id, mid) == b[id].second) l = mid+1;
else r = mid;
}
int x = cunt(id, l);
pq.push({id, l, x});
}
}
Compilation message
road_construction.cpp:3:52: warning: overflow in conversion from 'double' to 'int' changes value from '4.00000001e+9' to '2147483647' [-Woverflow]
3 | const int maxn = 250005, maxN = 1e6 + 5, INF = 4e9 + 10;
| ~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10055 ms |
4688 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10046 ms |
74056 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10055 ms |
74096 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10055 ms |
74096 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10055 ms |
4688 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10055 ms |
4688 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
