제출 #390117

#제출 시각아이디문제언어결과실행 시간메모리
390117apostoldaniel854Road Construction (JOI21_road_construction)C++14
0 / 100
10088 ms257076 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...