Submission #49848

#	Time	Username	Problem	Language	Result	Execution time	Memory
49848		zemen	Circle selection (APIO18_circle_selection)	C++17	87 / 100	3039 ms	58248 KiB

circle_selection

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

const int inf = 2e9 + 5;

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

  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;
}

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

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

  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 == inf;
  }
};

const int base = 1 << 19;
Bbox box[base * 2];
Circle cleaf[base * 2];
bool leaf[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, vector<Circle> t, bool byx) {
  assert(!t.empty());
  sort(t.begin(), t.end(), byx ? cmpx : cmpy);
  if (t.size() == 1) {
    endv[t[0].id] = v;
    leaf[v] = true;
    cleaf[v] = t[0];
    return;
  }
  int n = (int) t.size();
  vector<Circle> t2(t.begin() + n / 2, t.end());
  t.resize(n / 2);
  build(v * 2, t, !byx);
  build(v * 2 + 1, t2, !byx);
}

int lookup(const Circle& c, int v = 1) {
  if (!box[v].intersects(c)) {
    return inf;
  }
  if (leaf[v]) {
    if (cleaf[v].intersects(c)) {
      return cleaf[v].ord;
    } else {
      return inf;
    }
  }
  return min(lookup(c, v * 2), lookup(c, v * 2 + 1));
}

void turn_on(const Circle& c) {
  int v = endv[c.id];
  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;
    cs.push_back(c);
  }
  sort(cs.begin(), cs.end(), cmpr);
  for (int i = 0; i < (int) cs.size(); ++i) {
    cs[i].ord = i;
  }
  build(1, cs, true);

  vector<int> res(n);
  for (auto& c : cs) {
    int id = lookup(c);
    if (id == inf) {
      turn_on(c);
      id = c.id;
    } else {
      id = cs[id].id;
    }
    res[c.id] = id;
  }
  for (int x : res) {
    cout << x + 1 << ' ';
  }
  cout << '\n';
}

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