/**
* author: wxhtzdy
* created: 24.05.2022 08:24:38
**/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 2000000;
const int inf = (int) 1e11;
int root_u[MAX], root_d[MAX], tsz, ls[30 * MAX], rs[30 * MAX], rootU, rootD;
pair<int, int> mx[30 * MAX];
void build(int& node, int l, int r) {
node = ++tsz;
mx[node] = make_pair(-inf, l);
if (l == r) {
return;
}
int mid = l + r >> 1;
build(ls[node], l, mid);
build(rs[node], mid + 1, r);
}
void modify(int& node, int pnode, int l, int r, int i, int v) {
node = ++tsz;
ls[node] = ls[pnode];
rs[node] = rs[pnode];
if (l == r) {
mx[node] = make_pair(v, l);
return;
}
int mid = l + r >> 1;
if (i <= mid) {
modify(ls[node], ls[pnode], l, mid, i, v);
} else {
modify(rs[node], rs[pnode], mid + 1, r, i, v);
}
mx[node] = max(mx[ls[node]], mx[rs[node]]);
}
pair<int, int> query(int node, int l, int r, int ll, int rr) {
if (l > r || l > rr || r < ll || ll > rr) {
return make_pair(-inf, l);
}
if (ll <= l && r <= rr) {
return mx[node];
}
int mid = l + r >> 1;
return max(query(ls[node], l, mid, ll, rr), query(rs[node], mid + 1, r, ll, rr));
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> x(n);
vector<int> y(n);
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
}
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
if (x[i] != x[j]) {
return x[i] < x[j];
} else {
return y[i] > y[j];
}
});
vector<int> idx(n);
for (int i = 0; i < n; i++) {
idx[order[i]] = i;
}
vector<pair<int, int>> ys;
for (int i : order) {
ys.emplace_back(y[i], x[i]);
}
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
mx[0] = make_pair(-inf, 0);
int sz = 1;
while (sz < ys.size()) {
sz <<= 1;
}
build(rootU, 0, sz - 1);
build(rootD, 0, sz - 1);
int prv_u = rootU;
int prv_d = rootD;
auto GetId = [&](int i) {
return lower_bound(ys.begin(), ys.end(), make_pair(y[i], x[i])) - ys.begin();
};
for (int i : order) {
int j = GetId(i);
modify(root_u[i], prv_u, 0, sz - 1, j, x[i] + y[i]);
modify(root_d[i], prv_d, 0, sz - 1, j, x[i] - y[i]);
prv_u = root_u[i];
prv_d = root_d[i];
}
set<tuple<int, int, int, int>> st;
for (int i = 0; i < n; i++) {
int j = GetId(i);
{
auto val = query(root_u[i], 0, sz - 1, 0, j - 1);
if (val.first != -inf) {
st.insert(make_tuple(x[i] + y[i] - val.first, i, val.second, 0));
}
}
{
auto val = query(root_d[i], 0, sz - 1, j + 1, sz - 1);
if (val.first != -inf) {
st.insert(make_tuple(x[i] - y[i] - val.first, i, val.second, 1));
}
}
}
for (int b = 0; b < k; b++) {
auto it = st.begin();
cout << get<0>(*it) << '\n';
int i = get<1>(*it);
int p = get<2>(*it);
int d = get<3>(*it);
st.erase(it);
if (d == 0) {
modify(root_u[i], root_u[i], 0, sz - 1, p, -inf);
int j = GetId(i);
auto val = query(root_u[i], 0, sz - 1, 0, j - 1);
if (val.first != -inf) {
st.insert(make_tuple(x[i] + y[i] - val.first, i, val.second, 0));
}
} else {
modify(root_d[i], root_d[i], 0, sz - 1, p, -inf);
int j = GetId(i);
auto val = query(root_d[i], 0, sz - 1, j + 1, ys.size() - 1);
if (val.first != -inf) {
st.insert(make_tuple(x[i] - y[i] - val.first, i, val.second, 1));
}
}
}
return 0;
}
Compilation message
road_construction.cpp: In function 'void build(long long int&, long long int, long long int)':
road_construction.cpp:23:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | int mid = l + r >> 1;
| ~~^~~
road_construction.cpp: In function 'void modify(long long int&, long long int, long long int, long long int, long long int, long long int)':
road_construction.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
36 | int mid = l + r >> 1;
| ~~^~~
road_construction.cpp: In function 'std::pair<long long int, long long int> query(long long int, long long int, long long int, long long int, long long int)':
road_construction.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int mid = l + r >> 1;
| ~~^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:87:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | while (sz < ys.size()) {
| ~~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
414 ms |
89972 KB |
Output is correct |
2 |
Correct |
368 ms |
90096 KB |
Output is correct |
3 |
Correct |
345 ms |
89712 KB |
Output is correct |
4 |
Correct |
332 ms |
89764 KB |
Output is correct |
5 |
Correct |
416 ms |
88960 KB |
Output is correct |
6 |
Correct |
4 ms |
2016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1809 ms |
515996 KB |
Output is correct |
2 |
Correct |
1810 ms |
515960 KB |
Output is correct |
3 |
Correct |
209 ms |
89516 KB |
Output is correct |
4 |
Correct |
1218 ms |
515672 KB |
Output is correct |
5 |
Correct |
1274 ms |
515788 KB |
Output is correct |
6 |
Correct |
1316 ms |
515744 KB |
Output is correct |
7 |
Correct |
1244 ms |
515208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1811 ms |
385472 KB |
Output is correct |
2 |
Correct |
1841 ms |
385516 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
832 ms |
368688 KB |
Output is correct |
5 |
Correct |
1102 ms |
390716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1811 ms |
385472 KB |
Output is correct |
2 |
Correct |
1841 ms |
385516 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
832 ms |
368688 KB |
Output is correct |
5 |
Correct |
1102 ms |
390716 KB |
Output is correct |
6 |
Correct |
1899 ms |
390420 KB |
Output is correct |
7 |
Correct |
1906 ms |
390512 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1973 ms |
390532 KB |
Output is correct |
11 |
Correct |
833 ms |
368816 KB |
Output is correct |
12 |
Correct |
1081 ms |
390760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
414 ms |
89972 KB |
Output is correct |
2 |
Correct |
368 ms |
90096 KB |
Output is correct |
3 |
Correct |
345 ms |
89712 KB |
Output is correct |
4 |
Correct |
332 ms |
89764 KB |
Output is correct |
5 |
Correct |
416 ms |
88960 KB |
Output is correct |
6 |
Correct |
4 ms |
2016 KB |
Output is correct |
7 |
Correct |
1496 ms |
296464 KB |
Output is correct |
8 |
Correct |
1489 ms |
296628 KB |
Output is correct |
9 |
Correct |
303 ms |
89788 KB |
Output is correct |
10 |
Correct |
1120 ms |
295580 KB |
Output is correct |
11 |
Correct |
1344 ms |
295716 KB |
Output is correct |
12 |
Correct |
890 ms |
296304 KB |
Output is correct |
13 |
Correct |
920 ms |
294836 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
414 ms |
89972 KB |
Output is correct |
2 |
Correct |
368 ms |
90096 KB |
Output is correct |
3 |
Correct |
345 ms |
89712 KB |
Output is correct |
4 |
Correct |
332 ms |
89764 KB |
Output is correct |
5 |
Correct |
416 ms |
88960 KB |
Output is correct |
6 |
Correct |
4 ms |
2016 KB |
Output is correct |
7 |
Correct |
1809 ms |
515996 KB |
Output is correct |
8 |
Correct |
1810 ms |
515960 KB |
Output is correct |
9 |
Correct |
209 ms |
89516 KB |
Output is correct |
10 |
Correct |
1218 ms |
515672 KB |
Output is correct |
11 |
Correct |
1274 ms |
515788 KB |
Output is correct |
12 |
Correct |
1316 ms |
515744 KB |
Output is correct |
13 |
Correct |
1244 ms |
515208 KB |
Output is correct |
14 |
Correct |
1811 ms |
385472 KB |
Output is correct |
15 |
Correct |
1841 ms |
385516 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
832 ms |
368688 KB |
Output is correct |
18 |
Correct |
1102 ms |
390716 KB |
Output is correct |
19 |
Correct |
1899 ms |
390420 KB |
Output is correct |
20 |
Correct |
1906 ms |
390512 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1973 ms |
390532 KB |
Output is correct |
24 |
Correct |
833 ms |
368816 KB |
Output is correct |
25 |
Correct |
1081 ms |
390760 KB |
Output is correct |
26 |
Correct |
1496 ms |
296464 KB |
Output is correct |
27 |
Correct |
1489 ms |
296628 KB |
Output is correct |
28 |
Correct |
303 ms |
89788 KB |
Output is correct |
29 |
Correct |
1120 ms |
295580 KB |
Output is correct |
30 |
Correct |
1344 ms |
295716 KB |
Output is correct |
31 |
Correct |
890 ms |
296304 KB |
Output is correct |
32 |
Correct |
920 ms |
294836 KB |
Output is correct |
33 |
Correct |
2909 ms |
541312 KB |
Output is correct |
34 |
Correct |
2898 ms |
541484 KB |
Output is correct |
35 |
Correct |
2299 ms |
540428 KB |
Output is correct |
36 |
Correct |
1585 ms |
541304 KB |
Output is correct |
37 |
Correct |
1675 ms |
541140 KB |
Output is correct |
38 |
Correct |
1662 ms |
539860 KB |
Output is correct |