Submit Info #37766

Problem Lang User Status Time Memory
Convex Layers cpp bicsi AC 1565 ms 39.83 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
example_01 AC 1 ms 0.67 MiB
example_02 AC 1 ms 0.68 MiB
example_03 AC 0 ms 0.62 MiB
example_04 AC 1 ms 0.62 MiB
example_05 AC 2 ms 0.67 MiB
line_00 AC 300 ms 23.68 MiB
line_01 AC 387 ms 32.99 MiB
line_02 AC 110 ms 10.70 MiB
line_03 AC 429 ms 35.31 MiB
line_04 AC 26 ms 3.41 MiB
max_l_00 AC 500 ms 39.12 MiB
max_random_00 AC 1565 ms 39.52 MiB
max_random_01 AC 1557 ms 39.57 MiB
max_random_02 AC 1554 ms 39.50 MiB
max_random_03 AC 1558 ms 39.53 MiB
max_random_04 AC 1565 ms 39.56 MiB
max_square_grid_00 AC 762 ms 39.36 MiB
max_t_00 AC 537 ms 39.07 MiB
max_x_00 AC 566 ms 39.83 MiB
max_y_00 AC 594 ms 39.83 MiB

#include <bits/stdc++.h> using namespace std; using Point = complex<int>; using ll = long long; ll cross(Point a, Point b) { return 1LL * a.real() * b.imag() - 1LL * b.real() * a.imag(); } ll det(Point a, Point b, Point c) { return cross(b - a, c - a); } namespace std { bool operator<(const Point& a, const Point& b) { return make_pair(a.real(), a.imag()) < make_pair(b.real(), b.imag()); } } struct DynHull { struct Node { int bl, br, l, r, lc, rc; }; vector<Node> T = {{-1, -1, -1, -1, 0, 0}}; vector<Point> P; DynHull(vector<Point> P) : P(P) {} bool leaf(int x) { return T[x].l == T[x].r; } int combine(int lc, int rc, int ret = -1) { if (!lc || !rc) return lc + rc; if (ret == -1 || ret == lc || ret == rc) // (*) ret = T.size(), T.push_back({}); T[ret] = {-1, -1, T[lc].l, T[rc].r, lc, rc}; while (!leaf(lc) || !leaf(rc)) { int a = T[lc].bl, b = T[lc].br, c = T[rc].bl, d = T[rc].br; if (a != b && det(P[a], P[b], P[c]) > 0) { lc = T[lc].lc; } else if (c != d && det(P[b], P[c], P[d]) > 0) { rc = T[rc].rc; } else if (a == b) { rc = T[rc].lc; } else if (c == d) { lc = T[lc].rc; } else { auto s1 = det(P[a], P[b], P[c]), s2 = det(P[a], P[b], P[d]); assert(s1 >= s2); auto xc = P[c].real(), xd = P[d].real(), xm = P[T[rc].l].real(), xa = P[a].real(); if ((s1 * xd - s2 * xc < (s1 - s2) * xm) ^ (xa < xm)) { rc = T[rc].lc; } else { lc = T[lc].rc; } } } T[ret].bl = T[lc].l; T[ret].br = T[rc].l; return ret; } int Build(int b, int e) { if (e - b == 1) { T.push_back({b, b, b, b, 0, 0}); return T.size() - 1; } int m = (b + e) / 2; return combine(Build(b, m), Build(m, e)); } int Erase(int x, int pos) { if (!x || T[x].r < pos || T[x].l > pos) return x; return leaf(x) ? 0 : combine( Erase(T[x].lc, pos), Erase(T[x].rc, pos), x); } template<typename Callback> void Hull(int x, Callback&& cb, int l = 0, int r = 1e9) { if (!x || l > r) return; if (leaf(x)) { cb(T[x].l); return; } Hull(T[x].lc, cb, l, min(r, T[x].bl)); Hull(T[x].rc, cb, max(l, T[x].br), r); } }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<pair<Point, int>> pts(n); for (int i = 0; i < n; ++i) { int x, y; cin >> x >> y; pts[i] = make_pair(Point{x, y}, i); } sort(pts.begin(), pts.end()); vector<Point> P(n); vector<int> remap(n); for (int i = 0; i < n; ++i) { remap[i] = pts[i].second; P[i] = pts[i].first; } auto LH = DynHull(P); int lh = LH.Build(0, n); // for (int i = 0; i < n; ++i) P[i] = -P[i]; reverse(P.begin(), P.end()); auto UH = DynHull(P); int uh = UH.Build(0, n); vector<int> layer(n, -1); for (int i = 0; ; ++i) { vector<int> all; LH.Hull(lh, [&](int x) { all.push_back(x); }); UH.Hull(uh, [&](int x) { all.push_back(n - x - 1); }); if (all.empty()) break; for (auto x : all) { lh = LH.Erase(lh, x); uh = UH.Erase(uh, n - x - 1); layer[remap[x]] = i; } } for (int i = 0; i < n; ++i) cout << layer[i] + 1 << '\n'; return 0; }