#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x) cerr << #x << " " << x << "\n"
const int INF = 2e9;
const int MAX_N = 1e6;
vector <pair <ll, int>> v[1 + MAX_N];
int bin_search (vector <pair <ll, int>> &v, ll x) {
int n = v.size ();
int lb = 0, rb = n - 1, best = -1;
while (lb <= rb) {
int mid = (lb + rb) / 2;
if (v[mid].first <= x)
best = mid, lb = mid + 1;
else
rb = mid - 1;
}
return best;
}
struct aint_advanced {
int n;
vector <vector <pair <ll, int>>> seg;
aint_advanced (int n) {
this->n = n;
seg.resize (1 + 4 * n);
}
void build (int node, int lb, int rb) {
if (lb == rb) {
seg[node] = v[lb];
return;
}
int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
build (left_node, lb, mid);
build (right_node, mid + 1, rb);
seg[node].resize (seg[left_node].size () + seg[right_node].size ());
merge (seg[left_node].begin (), seg[left_node].end (), seg[right_node].begin (), seg[right_node].end (), seg[node].begin ());
}
void query_range (int node, int lb, int rb, int x1, int x2, ll y1, ll y2, vector <int> &pairs) {
if (x1 <= lb && rb <= x2) {
int start = bin_search (seg[node], y1 - 1) + 1;
int finish = bin_search (seg[node], y2);
for (int i = start; i <= finish; i++)
pairs.push_back (seg[node][i].second);
return;
}
int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
if (x1 <= mid)
query_range (left_node, lb, mid, x1, x2, y1, y2, pairs);
if (mid < x2)
query_range (right_node, mid + 1, rb, x1, x2, y1, y2, pairs);
}
};
struct aint_simple {
int n;
vector <vector <pair <ll, int>>> seg;
aint_simple (int n) {
this->n = n;
seg.resize (1 + 4 * n);
}
void build (int node, int lb, int rb) {
if (lb == rb) {
seg[node] = v[lb];
return;
}
int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
build (left_node, lb, mid);
build (right_node, mid + 1, rb);
seg[node].resize (seg[left_node].size () + seg[right_node].size ());
merge (seg[left_node].begin (), seg[left_node].end (), seg[right_node].begin (), seg[right_node].end (), seg[node].begin ());
}
ll query_range (int node, int lb, int rb, int x1, int x2, ll y1, ll y2) {
if (x1 <= lb && rb <= x2) {
int start = bin_search (seg[node], y1 - 1) + 1;
int finish = bin_search (seg[node], y2);
return finish - start + 1;
}
int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
ll ans = 0;
if (x1 <= mid)
ans += query_range (left_node, lb, mid, x1, x2, y1, y2);
if (mid < x2)
ans += query_range (right_node, mid + 1, rb, x1, x2, y1, y2);
return ans;
}
};
const int ERASE = 1, ADD = 0, QUERY = 2;
struct point_t {
int x;
int y;
};
vector <point_t> points;
struct event_t {
int type;
ll x1;
ll x2;
ll x;
ll y;
int idx;
bool operator < (const event_t &other) const {
if (y == other.y)
return type < other.type;
return y < other.y;
}
};
int n;
ll distance (point_t a, point_t b) {
return abs (a.x - b.x) + abs (a.y - b.y);
}
int k;
vector <point_t> true_points;
vector <ll> get_solution (ll max_distance) {
map <ll, int> norm;
for (int i = 0; i < n; i++) {
ll x1 = points[i].x - max_distance, x2 = points[i].x + max_distance;
norm[x1] = 0; norm[x2] = 0; norm[points[i].x] = 0;
}
int nr = 0;
for (auto &x : norm)
x.second = ++nr;
aint_advanced vertical (nr);
for (int i = 1; i <= nr; i++)
v[i].clear ();
for (int i = 0; i < n; i++)
v[norm[points[i].x]].push_back ({points[i].y, i});
for (int i = 1; i <= nr; i++)
sort (v[i].begin (), v[i].end ());
vertical.build (1, 1, nr);
vector <ll> sol;
for (int i = 0; i < n; i++) {
ll x1 = points[i].x - max_distance;
ll x2 = points[i].x + max_distance;
ll y1 = points[i].y - max_distance;
ll y2 = points[i].y + max_distance;
x1 = norm[x1], x2 = norm[x2];
vector <int> pairs;
vertical.query_range (1, 1, nr, x1, x2, y1, y2, pairs);
for (int it : pairs)
if (it < i)
sol.push_back (distance (true_points[i], true_points[it]));
}
sort (sol.begin (), sol.end ());
return sol;
}
ll check (ll max_distance) {
map <ll, int> norm;
for (int i = 0; i < n; i++) {
ll x1 = points[i].x - max_distance, x2 = points[i].x + max_distance;
norm[x1] = 0; norm[x2] = 0; norm[points[i].x] = 0;
}
int nr = 0;
for (auto &x : norm)
x.second = ++nr;
aint_simple vertical (nr);
for (int i = 1; i <= nr; i++)
v[i].clear ();
for (int i = 0; i < n; i++)
v[norm[points[i].x]].push_back ({points[i].y, i});
for (int i = 1; i <= nr; i++)
sort (v[i].begin (), v[i].end ());
vertical.build (1, 1, nr);
ll ans = 0;
for (int i = 0; i < n; i++) {
ll x1 = points[i].x - max_distance;
ll x2 = points[i].x + max_distance;
ll y1 = points[i].y - max_distance;
ll y2 = points[i].y + max_distance;
x1 = norm[x1], x2 = norm[x2];
ans += vertical.query_range (1, 1, nr, x1, x2, y1, y2) - 1;
}
return ans / 2;
}
int main () {
ios::sync_with_stdio (false);
cin.tie (0); cout.tie (0);
cin >> n >> k;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
true_points.push_back ({x, y});
points.push_back ({x + y, x - y});
}
ll best = 0;
ll lb = 0, rb = INF;
while (lb <= rb) {
ll mid = (lb + rb) / 2;
if (check (mid) <= k)
lb = mid + 1, best = mid;
else
rb = mid - 1;
}
vector <ll> sol = get_solution (best);
while ((int) sol.size () > k)
sol.pop_back ();
// dbg (best);
for (ll x : sol)
cout << x << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
29384 KB |
Output is correct |
| 2 |
Correct |
141 ms |
29336 KB |
Output is correct |
| 3 |
Incorrect |
99 ms |
28508 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10088 ms |
257076 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10088 ms |
256060 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10088 ms |
256060 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
29384 KB |
Output is correct |
| 2 |
Correct |
141 ms |
29336 KB |
Output is correct |
| 3 |
Incorrect |
99 ms |
28508 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
29384 KB |
Output is correct |
| 2 |
Correct |
141 ms |
29336 KB |
Output is correct |
| 3 |
Incorrect |
99 ms |
28508 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
