// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")
#include "bits/stdc++.h"
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>
using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
#define li long long
#define ld long double
#define ii pair<int, int>
#define dd pair<double, double>
#define lii pair<li, li>
#define ldd pair<ld, ld>
#define vi vector<int> // typedef vector<int> vi + #define int long long -> vi is still vector of 32 bit int, which took me 2 hours to figure out
#define vd vector<double>
// untested
#define vli vector<li>
#define vld vector<ld>
#define vii vector<ii>
#define vdd vector<dd>
#define vlii vector<lii>
#define vldd vector<ldd>
#define vvi vector<vi>
#define vvii vector<vii>
#define vvli vector<vli>
#define vvlii vector<vlii>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front
#define fr front
#define bc back
#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)
#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '
#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long // for convenience, not recommended
// #define double long double
void solve();
signed main() {
// freopen("input.inp","r",stdin);
// freopen("output.out","w",stdout);
// fastio();
int tc = 1;
fori(test, 1, tc) {
solve();
}
return 0;
}
#define int long long
const ld pi = 4 * atan(1.0), eps = 1e-9;
const int maxn = 2.5e5 + 5, inf = 1e13;
int n, k;
int x[maxn], y[maxn];
set<pair<int, ii> > all;
struct node {
ii mn = { inf, 0};
node * l = 0, * r = 0;
node(ii mn) : mn(mn), l(0), r(0) {};
node(node * l, node * r): l(l), r(r) {
if(l) mn = min(mn, l->mn);
if(r) mn = min(mn, r->mn);
}
};
node * build(int l, int r) {
if(l == r) return new node(ii(inf, inf));
int m = l + r >> 1; return new node(build(l, m), build(m + 1, r));
}
node* sett(node * now, int l, int r, int p, ii v) {
if(l == r) return new node(v);
int m = l + r >> 1; return p <= m? new node(sett(now->l, l, m, p, v), now->r): new node(now->l, sett(now->r, m + 1, r, p, v));
}
ii get(node *now, int l, int r, int ll, int rr) {
if(l > rr or ll > r) return {inf, 0};
if(ll <= l and r <= rr) return now->mn;
int m = l + r >> 1;
return min(get(now->l, l, m, ll, rr), get(now->r, m + 1, r, ll, rr));
}
void handle() {
vector<pair<ii, int> > pp;
fori(i, 1, n) pp.eb(ii(x[i], y[i]), i);
map<int, int> mm; for(auto t: pp) mm[t.fi.se] = 1; int tt = 0; for(auto &t: mm) t.se = ++tt;
vector<node*> vv(n + 1, 0);
set<pair<int, ii> > ss;
sort(all(pp)); reverse(all(pp));
node* last = build(1, n);
for(auto t: pp) {
int i = t.se;
// cout << x[i] << sp << y[i] << endl;
vv[i] = last;
ii mn = get(last, 1, n, mm[y[i]], n); //cout << mn.fi << endl;
ss.em(mn.fi - x[i] - y[i], ii(mn.se, i));
last = sett(last, 1, n, mm[y[i]], ii(x[i] + y[i], i));
}
fori(tm, 1, k) {
auto t = *begin(ss); int i = t.se.se, j = t.se.fi;
// cout << t.fi << endl;
if(t.fi >= inf) return;
ss.erase(t);
all.em(t.fi, ii(min(i, j), max(i, j)) );
vv[i] = sett(vv[i], 1, n, mm[y[j]], {inf, 0});
ii mn = get(vv[i], 1, n, mm[y[i]], n);
ss.em(mn.fi - x[i] - y[i], ii(mn.se, i));
// cout << "ss: " << ss.size() << endl;
// for(auto t: ss) cout << t.fi << sp; cout << endl;
}
}
void solve() {
cin >> n >> k;
fori(i, 1, n) {
cin >> x[i] >> y[i];
}
fori(tm, 0, 3) {
// cout << tm << endl;
fori(i,1, n) {
swap(x[i], y[i]);
x[i] = -x[i];
}
handle();
}
fori(i, 1, k) {
cout << begin(all)->fi << endl;
all.erase(begin(all));
}
}
Compilation message
road_construction.cpp: In function 'node* build(long long int, long long int)':
road_construction.cpp:95:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
95 | int m = l + r >> 1; return new node(build(l, m), build(m + 1, r));
| ~~^~~
road_construction.cpp: In function 'node* sett(node*, long long int, long long int, long long int, std::pair<long long int, long long int>)':
road_construction.cpp:99:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
99 | int m = l + r >> 1; return p <= m? new node(sett(now->l, l, m, p, v), now->r): new node(now->l, sett(now->r, m + 1, r, p, v));
| ~~^~~
road_construction.cpp: In function 'std::pair<long long int, long long int> get(node*, long long int, long long int, long long int, long long int)':
road_construction.cpp:104:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
104 | int m = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2759 ms |
552308 KB |
Output is correct |
| 2 |
Correct |
2787 ms |
552048 KB |
Output is correct |
| 3 |
Correct |
1600 ms |
525420 KB |
Output is correct |
| 4 |
Execution timed out |
10039 ms |
527516 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9578 ms |
1941572 KB |
Output is correct |
| 2 |
Correct |
9094 ms |
1941432 KB |
Output is correct |
| 3 |
Correct |
1254 ms |
525340 KB |
Output is correct |
| 4 |
Correct |
7282 ms |
1950968 KB |
Output is correct |
| 5 |
Correct |
9327 ms |
1935584 KB |
Output is correct |
| 6 |
Correct |
9019 ms |
1935724 KB |
Output is correct |
| 7 |
Correct |
9193 ms |
1940260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7344 ms |
1038972 KB |
Output is correct |
| 2 |
Correct |
7345 ms |
1040160 KB |
Output is correct |
| 3 |
Correct |
0 ms |
208 KB |
Output is correct |
| 4 |
Correct |
3848 ms |
1027492 KB |
Output is correct |
| 5 |
Correct |
3453 ms |
1028852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7344 ms |
1038972 KB |
Output is correct |
| 2 |
Correct |
7345 ms |
1040160 KB |
Output is correct |
| 3 |
Correct |
0 ms |
208 KB |
Output is correct |
| 4 |
Correct |
3848 ms |
1027492 KB |
Output is correct |
| 5 |
Correct |
3453 ms |
1028852 KB |
Output is correct |
| 6 |
Correct |
7411 ms |
1040184 KB |
Output is correct |
| 7 |
Correct |
7374 ms |
1040276 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
0 ms |
208 KB |
Output is correct |
| 10 |
Correct |
7108 ms |
1038952 KB |
Output is correct |
| 11 |
Correct |
3705 ms |
1027500 KB |
Output is correct |
| 12 |
Correct |
3528 ms |
1028876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2759 ms |
552308 KB |
Output is correct |
| 2 |
Correct |
2787 ms |
552048 KB |
Output is correct |
| 3 |
Correct |
1600 ms |
525420 KB |
Output is correct |
| 4 |
Execution timed out |
10039 ms |
527516 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2759 ms |
552308 KB |
Output is correct |
| 2 |
Correct |
2787 ms |
552048 KB |
Output is correct |
| 3 |
Correct |
1600 ms |
525420 KB |
Output is correct |
| 4 |
Execution timed out |
10039 ms |
527516 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
