#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
struct xy { int x, y, idx; }a[262626];
bool sort_x(xy a, xy b) {
if (a.x != b.x)return a.x < b.x;
return a.y < b.y;
}
bool sort_y(xy a, xy b) {
if (a.y != b.y)return a.y > b.y;
return a.x > b.x;
}
int T[2][1212121], TW[2][1212121], tn;
void insert_g(int type, int w, int g) {
T[type][tn + w] = g;
TW[type][tn + w] = tn+w;
for (int i = (w + tn) / 2; i > 0; i /= 2) {
T[type][i] = min(T[type][i * 2], T[type][i * 2 + 1]);
TW[type][i] = T[type][i * 2] <= T[type][i * 2 + 1] ? TW[type][i * 2] : TW[type][i * 2 + 1];
}
}
int n, k, mxv = 2e9+1;
pair<int, int>search_g(int type, int s, int e) {
s += tn; e += tn;
pair<int, int>res;
res.first = mxv;
while (s <= e) {
if (s % 2 == 1) {
if (res.first > T[type][s])res = { T[type][s],TW[type][s] };
s++;
}
if (e % 2 == 0) {
if (res.first > T[type][e])res = { T[type][e],TW[type][e] };
e--;
}
s /= 2; e /= 2;
}
return res;
}
vector<int>dd;
int f(int x, int flag) {
int i, j, pc;
vector<pair<int, int>>L, R;
for (i = 0; i < tn * 2; i++)T[0][i] = T[1][i] = mxv;
pc = 0; int ans = 0;
for (i = 0; i < n; i++) {
while (pc < k) {
auto sr = search_g(0, a[i].idx, n);
int v = sr.first, who = sr.second - tn;
if (v == mxv)break;
int res = v - a[i].x - a[i].y;
if (res > x)break;
if (flag) dd.push_back(res);
L.push_back({ v,who }); insert_g(0, who, mxv);
pc++;
}
while (pc < k) {
auto sr = search_g(1, 0, a[i].idx);
int v = sr.first, who = sr.second - tn;
if (v == mxv)break;
int res = v + a[i].x - a[i].y;
if (res > x)break;
if (flag) dd.push_back(res);
R.push_back({ v,who }); insert_g(1, who, mxv);
pc++;
}
for (auto v : L)insert_g(0, v.second, v.first);
for (auto v : R)insert_g(1, v.second, v.first);
L.clear(); R.clear();
insert_g(0, a[i].idx, a[i].x + a[i].y);
insert_g(1, a[i].idx, -a[i].x + a[i].y);
}
if (pc < k)return -1;
return 1;
}
int main() {
scanf("%d%d", &n, &k);
for (tn = 1; tn <= n; tn *= 2);
int i, j;
for (i = 0; i < n; i++)scanf("%d%d", &a[i].x, &a[i].y);
sort(a, a + n, sort_x);
for (i = 0; i < n; i++)a[i].idx = i;
sort(a, a + n, sort_y);
int s = 1, e = 2e9, ans = 0;
while (s <= e) {
int m = ((long long)s + e) / 2;
int R = f(m, 0);
if (R == -1) {
s = m + 1;
}
else {
e = m - 1;
ans = m;
}
}
f(ans - 1, 1);
sort(dd.begin(), dd.end());
for (auto v : dd)printf("%d\n", v);
for (i = dd.size(); i < k; i++)printf("%d\n", ans);
return 0;
}
Compilation message
road_construction.cpp: In function 'int f(int, int)':
road_construction.cpp:43:9: warning: unused variable 'j' [-Wunused-variable]
43 | int i, j, pc;
| ^
road_construction.cpp:46:14: warning: unused variable 'ans' [-Wunused-variable]
46 | pc = 0; int ans = 0;
| ^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:81:9: warning: unused variable 'j' [-Wunused-variable]
81 | int i, j;
| ^
road_construction.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%d%d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~
road_construction.cpp:82:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | for (i = 0; i < n; i++)scanf("%d%d", &a[i].x, &a[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1374 ms |
4024 KB |
Output is correct |
| 2 |
Correct |
1382 ms |
4052 KB |
Output is correct |
| 3 |
Incorrect |
1046 ms |
728 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4069 ms |
13560 KB |
Output is correct |
| 2 |
Correct |
4119 ms |
13608 KB |
Output is correct |
| 3 |
Correct |
1062 ms |
4112 KB |
Output is correct |
| 4 |
Correct |
3700 ms |
13300 KB |
Output is correct |
| 5 |
Correct |
4033 ms |
13608 KB |
Output is correct |
| 6 |
Correct |
3949 ms |
13588 KB |
Output is correct |
| 7 |
Correct |
3872 ms |
12884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5139 ms |
11300 KB |
Output is correct |
| 2 |
Correct |
5461 ms |
11284 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5139 ms |
11300 KB |
Output is correct |
| 2 |
Correct |
5461 ms |
11284 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1374 ms |
4024 KB |
Output is correct |
| 2 |
Correct |
1382 ms |
4052 KB |
Output is correct |
| 3 |
Incorrect |
1046 ms |
728 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1374 ms |
4024 KB |
Output is correct |
| 2 |
Correct |
1382 ms |
4052 KB |
Output is correct |
| 3 |
Incorrect |
1046 ms |
728 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
