Submission #49843

#	Time	Username	Problem	Language	Result	Execution time	Memory
49843		zemen	Circle selection (APIO18_circle_selection)	C++17	38 / 100	1668 ms	167128 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

struct Circle {
  int x, y, r, id;

  static ll sqr(ll x) {
    return x * x;
  }

  bool intersects(const Circle& c) const {
    return sqr(c.x - x) + sqr(c.y - y) <= sqr(r + c.r);
  }
};
istream& operator>>(istream& in, Circle& c) {
  return in >> c.x >> c.y >> c.r;
}

const ll infl = 1e18 + 7;

struct Bbox {
  ll xl, xr, yl, yr;

  Bbox() : xl(infl), xr(-infl), yl(infl), yr(-infl) {
  }

  void add(const Circle& c) {
    xl = min<ll>(xl, c.x - c.r);
    xr = max<ll>(xr, c.x + c.r);
    yl = min<ll>(yl, c.y - c.r);
    yr = max<ll>(yr, c.y + c.r);
  }

  bool intersects(const Circle& c) const {
    if (empty()) {
      return false;
    }
    if (c.x - c.r > xr || c.x + c.r < xl) {
      return false;
    }
    if (c.y - c.r > yr || c.y + c.r < yl) {
      return false;
    }
    return true;
  }

  bool empty() const {
    return xl == infl;
  }
};

const int base = 1 << 19;
vector<Circle> t[base * 2];
Bbox box[base * 2];
int endv[base];

bool cmpx(const Circle& a, const Circle& b) {
  return a.x < b.x || (a.x == b.x && a.y < b.y);
}

bool cmpy(const Circle& a, const Circle& b) {
  return a.y < b.y || (a.y == b.y && a.x < b.x);
}

bool cmpr(const Circle& a, const Circle& b) {
  return a.r > b.r || (a.r == b.r && a.id < b.id);
}

void build(int v, bool byx) {
  assert(!t[v].empty());
  sort(t[v].begin(), t[v].end(), byx ? cmpx : cmpy);
  if (t[v].size() == 1) {
    endv[t[v][0].id] = v;
    return;
  }
  int n = (int) t[v].size();
  t[v * 2].insert(t[v * 2].end(), t[v].begin(), t[v].begin() + n / 2);
  t[v * 2 + 1].insert(t[v * 2 + 1].end(), t[v].begin() + n / 2, t[v].end());
  build(v * 2, !byx);
  build(v * 2 + 1, !byx);
}

const int inf = 1e9;
int lookup(const Circle& c, int v = 1) {
  if (!box[v].intersects(c)) {
    return inf;
  }
  if (t[v].size() == 1) {
    if (t[v][0].intersects(c)) {
      return t[v][0].id;
    } else {
      return inf;
    }
  }
  return min(lookup(c, v * 2), lookup(c, v * 2 + 1));
}

void turn_on(int id) {
  int v = endv[id];
  const Circle& c = t[v][0];
  while (v >= 1) {
    box[v].add(c);
    v /= 2;
  }
}

signed main() {
#ifdef LOCAL
  assert(freopen("b.in", "r", stdin));
#endif
  int n;
  cin >> n;
  vector<Circle> cs;
  for (int i = 0; i < n; ++i) {
    Circle c;
    cin >> c;
    c.id = i;
    t[1].push_back(c);
    cs.push_back(c);
  }
  build(1, true);
  sort(cs.begin(), cs.end(), cmpr);
  vector<int> res(n);
  for (auto& c : cs) {
    int id = lookup(c);
    if (id == inf) {
      turn_on(c.id);
      id = c.id;
    }
    res[c.id] = id;
  }
  for (int x : res) {
    cout << x + 1 << ' ';
  }
  cout << '\n';
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13