Submit Info #33746

Problem Lang User Status Time Memory
Convex Layers cpp bicsi AC 2418 ms 324.15 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
example_01 AC 2 ms 0.60 MiB
example_02 AC 2 ms 0.62 MiB
example_03 AC 2 ms 0.67 MiB
example_04 AC 1 ms 0.62 MiB
example_05 AC 1 ms 0.67 MiB
line_00 AC 416 ms 125.15 MiB
line_01 AC 507 ms 149.64 MiB
line_02 AC 153 ms 49.73 MiB
line_03 AC 563 ms 167.09 MiB
line_04 AC 38 ms 13.04 MiB
max_l_00 AC 645 ms 201.51 MiB
max_random_00 AC 2418 ms 324.03 MiB
max_random_01 AC 2381 ms 324.14 MiB
max_random_02 AC 2353 ms 324.01 MiB
max_random_03 AC 2286 ms 324.14 MiB
max_random_04 AC 2288 ms 324.15 MiB
max_square_grid_00 AC 944 ms 252.51 MiB
max_t_00 AC 696 ms 211.41 MiB
max_x_00 AC 715 ms 210.64 MiB
max_y_00 AC 756 ms 218.76 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); } namespace DynHull { vector<Point> pts; struct Node { int bl, br, l, r; Node *lc = nullptr, *rc = nullptr; }; bool leaf(Node* x) { return x->l == x->r; } Node* combine(Node* lc, Node* rc) { if (!lc || !rc) return lc ?: rc; int64_t split_x = pts[rc->l].x; Node* ret = new Node({-1, -1, lc->l, rc->r, lc, rc}); while (!leaf(lc) || !leaf(rc)) { int a = lc->bl, b = lc->br, c = rc->bl, d = rc->br; if (a != b && det(pts[a], pts[b], pts[c]) > 0) { lc = lc->lc; } else if (c != d && det(pts[b], pts[c], pts[d]) > 0) { rc = rc->rc; } else if (a == b) { rc = rc->lc; } else if (c == d) { lc = lc->rc; } else { auto s1 = det(pts[a], pts[b], pts[c]); auto s2 = det(pts[b], pts[a], pts[d]); assert(s1 + s2 >= 0); if (s1 + s2 == 0 || s1 * pts[d].x + s2 * pts[c].x < split_x * (s1 + s2)) { lc = lc->rc; } else { rc = rc->lc; } } } ret->bl = lc->l; ret->br = rc->l; return ret; } void hull(Node* x, int l, int r, vector<int>& ret) { if (!x) return; l = max(l, x->l); r = min(r, x->r); if (l > r) return; if (leaf(x)) { ret.push_back(l); return; } hull(x->lc, max(l, x->l), min(r, x->bl), ret); hull(x->rc, max(l, x->br), min(r, x->r), ret); } vector<int> Hull(Node* x) { vector<int> ret; hull(x, 0, 1e9, ret); return ret; } Node* Erase(Node* x, int pos) { if (!x || x->l > pos || x->r < pos) return x; if (leaf(x)) return nullptr; return combine(Erase(x->lc, pos), Erase(x->rc, pos)); } Node* Build(int l, int r) { if (l == r) return new Node({l, l, l, l}); int m = (l + r) / 2; return combine(Build(l, m), Build(m + 1, r)); } } using namespace DynHull; int main() { int n; cin >> n; map<Point, int> mp; for (int i = 0; i < n; ++i) { int x, y; cin >> x >> y; pts.push_back(Point{x, y}); mp[pts[i]] = i; } sort(pts.begin(), pts.end()); for (int i = n - 1; i >= 0; --i) pts.push_back(-pts[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; for (auto x : Hull(lh)) all.push_back(x); for (auto x : Hull(uh)) all.push_back(2 * n - x - 1); if (all.empty()) break; for (auto x : all) { lh = Erase(lh, x); uh = Erase(uh, 2 * n - x - 1); layer[mp[pts[x]]] = i; } } for (int i = 0; i < n; ++i) cout << layer[i] + 1 << '\n'; return 0; }