/*
ID: varunra2
LANG: C++
TASK: road
*/
// we precalculate sqrt(n) smallest values of each point
// it is your value if it is to your left
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif
#define int long long
#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second
const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions
struct bit {
int n;
VI bit;
void init(int _n) {
n = _n;
bit.assign(n + 1, 0);
}
void upd(int ind, int val) {
// debug("in");
// debug(ind);
ind++;
while (ind <= n) {
bit[ind] += val;
ind += (ind & (-ind));
}
// debug("out");
}
int qry(int ind) {
int ret = 0;
// debug("indd");
ind++;
while (ind >= 1) {
ret += bit[ind];
ind -= (ind & (-ind));
}
// debug("outt");
return ret;
}
int qry(int l, int r) { return qry(r) - qry(l - 1); }
} fen;
int n, k;
VII vals;
MPII cmp;
VI pnts;
void init() { vals.resize(n); }
void transform() {
// convert all the points into chebyshev distance
for (int i = 0; i < n; i++) {
int x, y;
tie(x, y) = vals[i];
vals[i].x = x + y;
vals[i].y = x - y;
}
}
void comp() {
for (int i = 0; i < n; i++) {
pnts.PB(vals[i].y);
}
sort(all(pnts));
pnts.erase(unique(all(pnts)), pnts.end());
rep(i, 0, sz(pnts)) cmp[pnts[i]] = i;
}
bool count(int dist) {
fen.init(sz(pnts) + 2);
// VVI evnts;
// for (int i = 0; i < n; i++) {
// evnts.PB({vals[i].x, 0, i});
// evnts.PB({vals[i].x + dist, 1, i});
// }
// sort(all(evnts));
int p2 = 0;
int cnt = 0;
for (int i = 0; i < n; i++) {
// remove points
while (vals[i].x - vals[p2].x > dist) {
int pt = lower_bound(all(pnts), vals[p2].y) - pnts.begin();
fen.upd(pt, -1);
p2++;
}
// add contribution
int l = lower_bound(all(pnts), vals[i].y - dist) - pnts.begin();
auto p1 = upper_bound(all(pnts), vals[i].y + dist);
if (p1 != pnts.begin()) {
p1--;
int r = p1 - pnts.begin();
if (l <= r) {
cnt += fen.qry(l, r);
if (cnt >= k) return false;
}
}
// add new point
int pt = lower_bound(all(pnts), vals[i].y) - pnts.begin();
fen.upd(pt, 1);
}
return true;
}
int dst(int i, int j) {
return max(abs(vals[i].x - vals[j].x), abs(vals[i].y - vals[j].y));
}
VI gen(int dist) {
VI ret;
set<PII> st;
// VVI evnts;
// for (int i = 0; i < n; i++) {
// evnts.PB({vals[i].x, 0, i});
// evnts.PB({vals[i].x + dist, 1, i});
// }
// sort(all(evnts));
int p2 = 0;
for (int i = 0; i < n; i++) {
while (vals[i].x - vals[p2].x > dist) {
st.erase(MP(vals[p2].y, p2));
p2++;
}
auto it = st.lower_bound(MP(vals[i].y - dist, -1));
while (it != st.end()) {
if ((*it).x > vals[i].y + dist) break;
ret.PB(dst(i, (*it).y));
it++;
}
st.insert(MP(vals[i].y, i));
}
return ret;
}
int32_t main() {
// #ifndef ONLINE_JUDGE
// freopen("meetings2.in", "r", stdin);
// freopen("meetings2.out", "w", stdout);
// #endif
cin.sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
init();
trav(x, vals) cin >> x.x >> x.y;
transform();
sort(all(vals));
comp();
// int x = -1;
// for (int b = (int)4e9; b >= 1; b /= 2) {
// while (count(x + b)) x += b;
// }
// auto ret = gen(x);
int s = 0, e = 4e9;
while (s != e) {
int m = (s + e + 1) / 2;
if (count(m))
s = m;
else
e = m - 1;
}
if (k == 1) {
cout << s + 1 << '\n';
exit(0);
}
VI ret = gen(s);
while (sz(ret) < k) ret.PB(s + 1);
sort(all(ret));
trav(x, ret) cout << x << '\n';
debug(s + 1);
return 0;
}
Compilation message
road_construction.cpp: In function 'int32_t main()':
road_construction.cpp:22:20: warning: statement has no effect [-Wunused-value]
22 | #define debug(...) 42
| ^~
road_construction.cpp:233:3: note: in expansion of macro 'debug'
233 | debug(s + 1);
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
5084 KB |
Output is correct |
2 |
Correct |
61 ms |
5084 KB |
Output is correct |
3 |
Correct |
55 ms |
5212 KB |
Output is correct |
4 |
Correct |
54 ms |
5212 KB |
Output is correct |
5 |
Correct |
54 ms |
4060 KB |
Output is correct |
6 |
Correct |
3 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1262 ms |
27240 KB |
Output is correct |
2 |
Correct |
1275 ms |
27164 KB |
Output is correct |
3 |
Correct |
50 ms |
5084 KB |
Output is correct |
4 |
Correct |
1193 ms |
27008 KB |
Output is correct |
5 |
Correct |
1101 ms |
27236 KB |
Output is correct |
6 |
Correct |
1031 ms |
27364 KB |
Output is correct |
7 |
Correct |
938 ms |
26980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1924 ms |
24012 KB |
Output is correct |
2 |
Correct |
2325 ms |
23892 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
918 ms |
23928 KB |
Output is correct |
5 |
Correct |
556 ms |
6504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1924 ms |
24012 KB |
Output is correct |
2 |
Correct |
2325 ms |
23892 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
918 ms |
23928 KB |
Output is correct |
5 |
Correct |
556 ms |
6504 KB |
Output is correct |
6 |
Correct |
2592 ms |
24036 KB |
Output is correct |
7 |
Correct |
2559 ms |
23892 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
2616 ms |
22628 KB |
Output is correct |
11 |
Correct |
690 ms |
24036 KB |
Output is correct |
12 |
Correct |
723 ms |
6504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
5084 KB |
Output is correct |
2 |
Correct |
61 ms |
5084 KB |
Output is correct |
3 |
Correct |
55 ms |
5212 KB |
Output is correct |
4 |
Correct |
54 ms |
5212 KB |
Output is correct |
5 |
Correct |
54 ms |
4060 KB |
Output is correct |
6 |
Correct |
3 ms |
364 KB |
Output is correct |
7 |
Correct |
1686 ms |
13968 KB |
Output is correct |
8 |
Correct |
1666 ms |
13828 KB |
Output is correct |
9 |
Correct |
54 ms |
5212 KB |
Output is correct |
10 |
Correct |
1320 ms |
12280 KB |
Output is correct |
11 |
Correct |
953 ms |
11652 KB |
Output is correct |
12 |
Correct |
428 ms |
6892 KB |
Output is correct |
13 |
Correct |
470 ms |
5524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
5084 KB |
Output is correct |
2 |
Correct |
61 ms |
5084 KB |
Output is correct |
3 |
Correct |
55 ms |
5212 KB |
Output is correct |
4 |
Correct |
54 ms |
5212 KB |
Output is correct |
5 |
Correct |
54 ms |
4060 KB |
Output is correct |
6 |
Correct |
3 ms |
364 KB |
Output is correct |
7 |
Correct |
1262 ms |
27240 KB |
Output is correct |
8 |
Correct |
1275 ms |
27164 KB |
Output is correct |
9 |
Correct |
50 ms |
5084 KB |
Output is correct |
10 |
Correct |
1193 ms |
27008 KB |
Output is correct |
11 |
Correct |
1101 ms |
27236 KB |
Output is correct |
12 |
Correct |
1031 ms |
27364 KB |
Output is correct |
13 |
Correct |
938 ms |
26980 KB |
Output is correct |
14 |
Correct |
1924 ms |
24012 KB |
Output is correct |
15 |
Correct |
2325 ms |
23892 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
918 ms |
23928 KB |
Output is correct |
18 |
Correct |
556 ms |
6504 KB |
Output is correct |
19 |
Correct |
2592 ms |
24036 KB |
Output is correct |
20 |
Correct |
2559 ms |
23892 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
2616 ms |
22628 KB |
Output is correct |
24 |
Correct |
690 ms |
24036 KB |
Output is correct |
25 |
Correct |
723 ms |
6504 KB |
Output is correct |
26 |
Correct |
1686 ms |
13968 KB |
Output is correct |
27 |
Correct |
1666 ms |
13828 KB |
Output is correct |
28 |
Correct |
54 ms |
5212 KB |
Output is correct |
29 |
Correct |
1320 ms |
12280 KB |
Output is correct |
30 |
Correct |
953 ms |
11652 KB |
Output is correct |
31 |
Correct |
428 ms |
6892 KB |
Output is correct |
32 |
Correct |
470 ms |
5524 KB |
Output is correct |
33 |
Correct |
4282 ms |
28036 KB |
Output is correct |
34 |
Correct |
4313 ms |
28032 KB |
Output is correct |
35 |
Correct |
3856 ms |
23092 KB |
Output is correct |
36 |
Correct |
799 ms |
10216 KB |
Output is correct |
37 |
Correct |
720 ms |
10468 KB |
Output is correct |
38 |
Correct |
973 ms |
9572 KB |
Output is correct |