Submit Info #37734

Problem Lang User Status Time Memory
Convex Layers cpp bicsi AC 1897 ms 49.10 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
example_01 AC 1 ms 0.64 MiB
example_02 AC 1 ms 0.67 MiB
example_03 AC 2 ms 0.67 MiB
example_04 AC 1 ms 0.65 MiB
example_05 AC 1 ms 0.67 MiB
line_00 AC 363 ms 27.34 MiB
line_01 AC 460 ms 44.50 MiB
line_02 AC 139 ms 12.71 MiB
line_03 AC 516 ms 46.00 MiB
line_04 AC 31 ms 3.91 MiB
max_l_00 AC 585 ms 49.06 MiB
max_random_00 AC 1864 ms 48.98 MiB
max_random_01 AC 1850 ms 49.10 MiB
max_random_02 AC 1897 ms 48.99 MiB
max_random_03 AC 1865 ms 49.00 MiB
max_random_04 AC 1846 ms 49.06 MiB
max_square_grid_00 AC 830 ms 49.02 MiB
max_t_00 AC 624 ms 49.00 MiB
max_x_00 AC 648 ms 49.02 MiB
max_y_00 AC 688 ms 49.00 MiB

#include <bits/stdc++.h> using namespace std; struct Point{ int64_t x,y; Point operator-(Point p)const{ return {x-p.x,y-p.y}; } int64_t cross(Point p)const{ return x*p.y-y*p.x; } int64_t dot(Point p)const{ return x*p.x+y*p.y; } bool operator<(Point p)const{ if(x!=p.x) return x<p.x; return y<p.y; } bool operator==(Point p)const{ return x==p.x&&y==p.y; } Point operator-()const{ return {-x,-y}; } }; int64_t det(Point a,Point b,Point c){ return (b-a).cross(c-a); } struct Node { int bl, br, l, r, lc, rc; }; vector<Node> T = {{-1, -1, -1, -1, 0, 0}}; vector<Point> 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]); auto s2 = det(P[b], P[a], P[d]); assert(s1 + s2 >= 0); if (s1 + s2 == 0 || s1 * P[d].x + s2 * P[c].x < P[T[rc].l].x * (s1 + s2)) { lc = T[lc].rc; } else { rc = T[rc].lc; } } } T[ret].bl = T[lc].l; T[ret].br = T[rc].l; return ret; } void Hull(int x, int l, int r, vector<int>& ret) { if (!x || l > r) return; if (leaf(x)) { ret.push_back(l); return; } Hull(T[x].lc, l, min(r, T[x].bl), ret); Hull(T[x].rc, max(l, T[x].br), r, ret); } int Erase(int x, int pos) { if (!x || T[x].l > pos || T[x].r < pos) return x; if (leaf(x)) return 0; return combine(Erase(T[x].lc, pos), Erase(T[x].rc, pos), x); } int Build(int l, int r) { if (l == r) { T.push_back({l, l, l, l, 0, 0}); return T.size() - 1; } int m = (l + r) / 2; return combine(Build(l, m), Build(m + 1, r)); } int main() { int n; cin >> n; map<Point, int> mp; for (int i = 0; i < n; ++i) { int x, y; cin >> x >> y; P.push_back({x, y}); mp[P[i]] = i; } sort(P.begin(), P.end()); for (int i = n - 1; i >= 0; --i) P.push_back(-P[i]); auto lh = Build(0, n - 1), uh = Build(n, 2 * n - 1); vector<int> layer(n, -1); for (int i = 0; ; ++i) { vector<int> all; Hull(lh, T[lh].l, T[lh].r, all); Hull(uh, T[uh].l, T[uh].r, all); if (all.empty()) break; for (auto x : all) { if (x >= n) x = 2 * n - x - 1; lh = Erase(lh, x); uh = Erase(uh, 2 * n - x - 1); layer[mp[P[x]]] = i; } } for (int i = 0; i < n; ++i) cout << layer[i] + 1 << '\n'; return 0; }