Submit Info #27521

Problem Lang User Status Time Memory
Convex Layers cpp Jeffrey AC 618 ms 79.40 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
example_01 AC 0 ms 0.65 MiB
example_02 AC 0 ms 0.62 MiB
example_03 AC 0 ms 0.62 MiB
example_04 AC 1 ms 0.67 MiB
example_05 AC 0 ms 0.61 MiB
line_00 AC 179 ms 51.66 MiB
line_01 AC 216 ms 61.27 MiB
line_02 AC 68 ms 21.98 MiB
line_03 AC 245 ms 67.72 MiB
line_04 AC 18 ms 6.61 MiB
max_l_00 AC 283 ms 79.40 MiB
max_random_00 AC 618 ms 70.28 MiB
max_random_01 AC 604 ms 70.27 MiB
max_random_02 AC 559 ms 70.27 MiB
max_random_03 AC 602 ms 70.27 MiB
max_random_04 AC 595 ms 70.27 MiB
max_square_grid_00 AC 299 ms 70.15 MiB
max_t_00 AC 287 ms 77.01 MiB
max_x_00 AC 249 ms 70.52 MiB
max_y_00 AC 251 ms 70.53 MiB

#include <iostream> #include <algorithm> #include <vector> #include <string> #include <cmath> #include <cassert> #include <map> #include <set> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int mod = 1000000007; struct Point{ Point& operator+=(Point const&o) { x+=o.x; y+=o.y; return *this; } Point& operator-=(Point const&o) { x-=o.x; y-=o.y; return *this; } Point operator-() const { return Point{-x, -y}; } friend Point operator+(Point a, Point const&b){ a+=b; return a; } friend Point operator-(Point a, Point const&b){ a-=b; return a; } friend ll dot(Point const&a, Point const&b){ return a.x*b.x + a.y*b.y; } friend ll cross(Point const&a, Point const&b){ return a.x*b.y - a.y*b.x; } friend bool operator<(Point const&a, Point const&b){ return tie(a.x, a.y) < tie(b.x, b.y); } ll x=0, y=0; }; int ccw(Point const&a, Point const&b){ ll x = cross(a, b); return (x>0)-(x<0); } int ccw(Point const&a, Point const&b, Point const&c){ return ccw(b-a, c-a); } // Decremental convex hull in O(n log n) // From "Applications of a semi-dynamic convex hull algorithm" by J. Hershberger and S. Suri struct Upper_Hull{ struct Link{ Point p; Link *prev = nullptr, *next = nullptr; int id; }; struct Node{ Link *chain, *chain_back; Link *tangent; }; template<typename S, typename T> pair<Link*, Link*> find_bridge(Link*l, Link*r, S next, T convex){ while(next(l) || next(r)){ if(!next(r) || (next(l) && convex(Point{0, 0}, next(l)->p - l->p, next(r)->p - r->p))){ if(convex(l->p, next(l)->p, r->p)){ l = next(l); } else { break; } } else { if(!convex(l->p, r->p, next(r)->p)){ r = next(r); } else { break; } } } return {l, r}; } template<bool rev = false> void fix_chain(int u, Link*l, Link*r){ if(rev){ // l and r to the right of actual bridge tie(r, l) = find_bridge(r, l, [](Link*x){ return x->prev; }, [](Point const&a, Point const&b, Point const&c){ return ccw(a, b, c) >= 0; }); } else { // l and r to the left of actual bridge tie(l, r) = find_bridge(l, r, [](Link*x){ return x->next; }, [](Point const&a, Point const&b, Point const&c){ return ccw(a, b, c) <= 0; }); } tree[u].tangent = l; tree[u].chain = tree[2*u].chain; tree[u].chain_back = tree[2*u+1].chain_back; tree[2*u].chain = l->next; tree[2*u+1].chain_back = r->prev; if(l->next){ l->next->prev = nullptr; } else { tree[2*u].chain_back = nullptr; } if(r->prev){ r->prev->next = nullptr; } else { tree[2*u+1].chain = nullptr; } l->next = r; r->prev = l; } void build(int u, int a, int b){ if(b-a == 1){ tree[u].chain = tree[u].chain_back = &lists[a]; tree[u].tangent = nullptr; return; } const int m = a + (b-a)/2; build(2*u, a, m); build(2*u+1, m, b); auto l = tree[2*u].chain, r = tree[2*u+1].chain; fix_chain(u, l, r); } void rob(int u, int v){ tree[u].chain = tree[v].chain; tree[v].chain = nullptr; tree[u].chain_back = tree[v].chain_back; tree[v].chain_back = nullptr; } void remove(int u, int a, int b, int const&i){ if(i < a || i >= b) return; // we should never hit a leaf assert(b-a > 1); const int m = a + (b-a)/2; // one child -> that child contains i if(!tree[u].tangent){ int v = i<m ? 2*u : 2*u+1; tree[v].chain = tree[u].chain; tree[v].chain_back = tree[u].chain_back; if(i < m){ remove(2*u, a, m, i); } else { remove(2*u+1, m, b, i); } rob(u, v); return; } // restore hull of children auto l = tree[u].tangent, r = l->next; l->next = tree[2*u].chain; if(tree[2*u].chain){ tree[2*u].chain->prev = l; } else { tree[2*u].chain_back = l; } tree[2*u].chain = tree[u].chain; r->prev = tree[2*u+1].chain_back; if(tree[2*u+1].chain_back){ tree[2*u+1].chain_back->next = r; } else { tree[2*u+1].chain = r; } tree[2*u+1].chain_back = tree[u].chain_back; // delete i const int v = i<m ? 2*u : 2*u+1; // only i if(tree[v].chain == tree[v].chain_back && tree[v].chain->id == i){ tree[v].chain = tree[v].chain_back = nullptr; rob(u, v^1); tree[u].tangent = nullptr; return; } if(i < m){ if(l->id == i){ l = l->next; } remove(2*u, a, m, i); if(!l){ l = tree[2*u].chain_back; } fix_chain<true>(u, l, r); } else { if(r->id == i){ r = r->prev; } remove(2*u+1, m, b, i); if(!r){ r = tree[2*u+1].chain; } fix_chain<false>(u, l, r); } } void remove(int i){ // i is the only point if(tree[1].chain == tree[1].chain_back){ tree[1].chain = tree[1].chain_back = nullptr; return; } remove(1, 0, n, i); } Upper_Hull(vector<Point> const&v) : n(v.size()), tree(4*n), lists(n){ assert(is_sorted(v.begin(), v.end())); for(int i=0; i<n; ++i){ lists[i].p = v[i]; lists[i].id = i; } build(1, 0, n); } vector<int> get_hull(){ vector<int> ret; for(Link* u = tree[1].chain; u; u=u->next){ ret.push_back(u->id); } return ret; } vector<Point> get_hull_points(){ vector<Point> ret; for(Link* u = tree[1].chain; u; u=u->next){ ret.push_back(u->p); } return ret; } int n; vector<Node> tree; vector<Link> lists; }; // test code from https://codeforces.com/blog/entry/75929 signed main(){ int N; scanf("%d",&N); vector<int> layer(N); vector<int> ans(N); vector<Point> ps; map<Point,int> id; for(int i=0;i<N;i++){ int X,Y; scanf("%d %d",&X,&Y); ps.push_back({X,Y}); id[{X,Y}]=i; } sort(ps.begin(),ps.end()); Upper_Hull left(ps); reverse(ps.begin(),ps.end()); for(auto& p:ps){ p=-p; } Upper_Hull right(ps); for(auto& p:ps){ p=-p; } reverse(ps.begin(),ps.end()); for(int l=1,cnt=0;cnt<N;l++){ set<int> hull; for(int i:left.get_hull()){ hull.insert(i); } for(int i:right.get_hull()){ hull.insert(N-1-i); } for(int i:hull){ assert(!layer[i]); cnt++; layer[i]=l; left.remove(i); right.remove(N-1-i); } } for(int i=0;i<N;i++){ ans[id[ps[i]]]=layer[i]; } for(int i=0;i<N;i++){ printf("%d\n",ans[i]); } return 0; }