Submission #397178

#TimeUsernameProblemLanguageResultExecution timeMemory
39717812tqianRoad Construction (JOI21_road_construction)C++17
100 / 100
4209 ms676112 KiB
#include <bits/stdc++.h> using namespace std; #define f1r(i, a, b) for (int i = a; i < b; ++i) #define f0r(i, a) f1r(i, 0, a) #define each(t, a) for (auto& t : a) #define mp make_pair #define f first #define s second #define pb push_back #define eb emplace_back #define sz(x) (int)(x).size() #define all(x) begin(x), end(x) typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef vector<pi> vpi; typedef vector<pl> vpl; template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } const int M = 4e7; const int INF = 2e9 + 7; struct Node { int lc, rc; int mx = -INF; int loc = -INF; } t[M]; int cnt = 0; int modify(int p, int l, int r, int x, int v) { int u = ++cnt; if (l == r) { t[u].mx = v; t[u].loc = l; } else { int m = (l + r) >> 1; if (x <= m) { t[u].lc = modify(t[p].lc, l, m, x, v); t[u].rc = t[p].rc; } else { t[u].lc = t[p].lc; t[u].rc = modify(t[p].rc, m + 1, r, x, v); } int L = t[t[u].lc].mx; int R = t[t[u].rc].mx; if (L > R) { t[u].mx = L; t[u].loc = t[t[u].lc].loc; } else { t[u].mx = R; t[u].loc = t[t[u].rc].loc; } } return u; } pi query(int p, int l, int r, int lo, int hi) { if (hi < l || r < lo) return {-INF, -INF};; if (lo <= l && r <= hi) return {t[p].mx, t[p].loc}; int m = (l + r) >> 1; return max(query(t[p].lc, l, m, lo, hi), query(t[p].rc, m + 1, r ,lo, hi)); } int new_node() { ++cnt; t[cnt].lc = t[cnt].rc = cnt; t[cnt].mx = -INF; t[cnt].loc = -INF; return cnt; } template <class T> int get_pos(vector<T>& v, T x) { return lower_bound(all(v), x) - v.begin(); } void reset() { f0r(i, cnt + 1) { t[i].lc = t[i].rc = 0; t[i].mx = t[i].loc = -INF; } cnt = 0; } int main() { cin.tie(0)->sync_with_stdio(0); int n, k; cin >> n >> k; vpi pts(n); f0r(i, n) { cin >> pts[i].f >> pts[i].s; } vi xvals; vi yvals; typedef pair<ll, int> T; priority_queue<T, vector<T>, greater<T>> pq; vl dists; { // diagonally up, not equal x or y reset(); while (!pq.empty()) pq.pop(); xvals.clear(); yvals.clear(); sort(all(pts)); f0r(i, n) { xvals.pb(pts[i].f); yvals.pb(pts[i].s); } xvals.pb(-INF); yvals.pb(-INF); sort(all(xvals)); sort(all(yvals)); xvals.erase(unique(all(xvals)), xvals.end()); yvals.erase(unique(all(yvals)), yvals.end()); int nx = sz(xvals); int ny = sz(yvals); vector<vi> by_x(nx); vector<vi> by_y(ny); each(p, pts) { by_x[get_pos(xvals, p.f)].pb(p.s); by_y[get_pos(yvals, p.s)].pb(p.f); } each(y, by_y) sort(all(y)); vi seg(n); // corresponding segtree for each point int rec = new_node(); f0r(i, nx) { // iterate over xvals each(p, by_x[i]) { // this is before for exclusive int x = xvals[i]; int y = p; int pid = get_pos(pts, mp(x, y)); seg[pid] = rec; } each(p, by_x[i]) { int x = xvals[i]; int y = p; int id = get_pos(yvals, y); rec = modify(rec, 0, ny - 1, id, x + y); } } auto add = [&](int i) { int x = pts[i].f; int y = pts[i].s; int yid = get_pos(yvals, y); auto res = query(seg[i], 0, ny - 1, 0, yid - 1); // check next point if (res.f == -INF) return; ll dist = 0LL + x + y - res.f; pq.push(mp(dist, i)); }; auto nullify = [&](int i) { int x = pts[i].f; int y = pts[i].s; int yid = get_pos(yvals, y); auto res = query(seg[i], 0, ny - 1, 0, yid - 1); // exclusive assert(res.f != -INF); int loc = res.s; int xloc = res.f - yvals[loc]; int xid = get_pos(by_y[loc], xloc); if (xid == 0) { seg[i] = modify(seg[i], 0, ny - 1, loc, -INF); // set to null } else { seg[i] = modify(seg[i], 0, ny - 1, loc, yvals[loc] + by_y[loc][xid - 1]); // set to null } }; f0r(i, n) { int x = pts[i].f; int y = pts[i].s; int yid = get_pos(yvals, y); auto res = query(seg[i], 0, ny - 1, 0, yid - 1); // exclusive if (res.f == -INF) continue; ll dist = 0LL + x + y - res.f; dists.pb(dist); // initial dist nullify(i); add(i); } int t = 0; while (t < k && !pq.empty()) { auto top = pq.top(); pq.pop(); dists.pb(top.f); int i = top.s; nullify(i); add(i); t++; } } { // possibly equal x, y reset(); while (!pq.empty()) pq.pop(); xvals.clear(); yvals.clear(); f0r(i, n) pts[i].f *= -1; sort(all(pts)); f0r(i, n) { xvals.pb(pts[i].f); yvals.pb(pts[i].s); } xvals.pb(-INF); yvals.pb(-INF); sort(all(xvals)); sort(all(yvals)); xvals.erase(unique(all(xvals)), xvals.end()); yvals.erase(unique(all(yvals)), yvals.end()); int nx = sz(xvals); int ny = sz(yvals); vector<vi> by_x(nx); vector<vi> by_y(ny); each(p, pts) { by_x[get_pos(xvals, p.f)].pb(p.s); by_y[get_pos(yvals, p.s)].pb(p.f); } each(y, by_y) sort(all(y)); vi seg(n); // corresponding segtree for each point int rec = new_node(); f0r(i, nx) { // iterate over xvals each(p, by_x[i]) { int x = xvals[i]; int y = p; int id = get_pos(yvals, y); rec = modify(rec, 0, ny - 1, id, x + y); } each(p, by_x[i]) { // this is before for exclusive int x = xvals[i]; int y = p; int pid = get_pos(pts, mp(x, y)); seg[pid] = rec; } } auto add = [&](int i) { int x = pts[i].f; int y = pts[i].s; int yid = get_pos(yvals, y); auto res = query(seg[i], 0, ny - 1, 0, yid); // check next point if (res.f == -INF) return; ll dist = 0LL + x + y - res.f; pq.push(mp(dist, i)); }; auto nullify = [&](int i) { int x = pts[i].f; int y = pts[i].s; int yid = get_pos(yvals, y); auto res = query(seg[i], 0, ny - 1, 0, yid); assert(res.f != -INF); int loc = res.s; int xloc = res.f - yvals[loc]; int xid = get_pos(by_y[loc], xloc); if (xid == 0) { seg[i] = modify(seg[i], 0, ny - 1, loc, -INF); // set to null } else { seg[i] = modify(seg[i], 0, ny - 1, loc, yvals[loc] + by_y[loc][xid - 1]); // set to null } }; f0r(i, n) { int x = pts[i].f; int y = pts[i].s; int yid = get_pos(yvals, y); auto res = query(seg[i], 0, ny - 1, 0, yid); // exclusive if (res.f == -INF) continue; int loc = res.s; ll dist = 0LL + x + y - res.f; assert(dist == 0); nullify(i); add(i); } int t = 0; while (t < k && !pq.empty()) { auto top = pq.top(); pq.pop(); dists.pb(top.f); int i = top.s; nullify(i); add(i); t++; } } sort(all(dists)); f0r(i, k) { cout << dists[i] << '\n'; } return 0; } /** * we have to pursue from a few directions * can have equal y coordinate, but not x coordinate * */

Compilation message (stderr)

road_construction.cpp: In lambda function:
road_construction.cpp:182:17: warning: unused variable 'x' [-Wunused-variable]
  182 |             int x = pts[i].f;
      |                 ^
road_construction.cpp: In lambda function:
road_construction.cpp:306:17: warning: unused variable 'x' [-Wunused-variable]
  306 |             int x = pts[i].f;
      |                 ^
road_construction.cpp: In function 'int main()':
road_construction.cpp:336:17: warning: unused variable 'loc' [-Wunused-variable]
  336 |             int loc = res.s;
      |                 ^~~
#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...