제출 #966677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
966677		Soumya1	원 고르기 (APIO18_circle_selection)	C++17	72 / 100	3097 ms	202128 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
const int mxN = 3e5 + 5;
int x[mxN], y[mxN], r[mxN], pos[mxN], ans[mxN];
set<pair<int, int>> st[2 * 4 * mxN];
int base;
char rr;
void rf(int &x) {
  x = 0;
  int sgn = 0;
  while (rr < 48 && rr != '-') rr = getchar();
  if (rr == '-') { sgn = 1; rr = getchar(); }
  while (47 < rr) { x = (x << 3) + (x << 1) + (rr & 15); rr = getchar(); }
  if (sgn) x = -x;
}
void upd(int p, int q, int i) {
  p += base; q += base;
  p--; q--;
  while (p <= q) {
    if (p & 1) st[p++].insert({y[i], i});
    if (~q & 1) st[q--].insert({y[i], i});
    p >>= 1; q >>= 1;
  }
}
void update(int a, int b) {
  if (pos[b] < pos[ans[a]] && 1LL * (x[a] - x[b]) * (x[a] - x[b]) + 1LL * (y[a] - y[b]) * (y[a] - y[b]) <= 1LL * (r[a] + r[b]) * (r[a] + r[b]))
    ans[a] = b;
}
void check(int x, int i) {
  auto it = lower_bound(st[x].begin(), st[x].end(), pair<int, int> {y[i], -2e9});
  if (it != st[x].end()) {
    update(i, (*it).second);
    it++;
    if (it != st[x].end()) {
      update(i, (*it).second);
    }
  }
  it = lower_bound(st[x].begin(), st[x].end(), pair<int, int> {y[i], -2e9});
  if (it != st[x].begin()) {
    it--;
    update(i, (*it).second);
    if (it != st[x].begin()) {
      it--;
      update(i, (*it).second);
    }
  }
}
void get(int p, int i) {
  p += base; p--;
  while (p >= 1) {
    check(p, i);
    p >>= 1;
  }
}
void testCase() {
  int n;
  rf(n);
  vector<int> vx, vy;
  for (int i = 0; i < n; i++) {
    rf(x[i]), rf(y[i]), rf(r[i]);
    vx.push_back(x[i] - r[i]);
    vx.push_back(x[i] + r[i]); 
    vy.push_back(y[i] - r[i]);
    vy.push_back(y[i] + r[i]); 
  }
  sort(vx.begin(), vx.end());
  vx.erase(unique(vx.begin(), vx.end()), vx.end());
  sort(vy.begin(), vy.end());
  vy.erase(unique(vy.begin(), vy.end()), vy.end());
  vector<int> v;
  if (vx.size() < vy.size()) {
    for (int i = 0; i < n; i++) swap(x[i], y[i]);
    v = vy;
  } else {
    v = vx;
  }
  vector<int> ord(n);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int i, int j) {
    if (r[i] != r[j]) return r[i] > r[j];
    return i < j;
  });
  for (int i = 0; i < n; i++) {
    pos[ord[i]] = i;
  }
  int N = v.size();
  for (base = 1; base < N; base <<= 1);
  for (int i = 0; i < n; i++) ans[i] = i;
  for (int i = 0; i < n; i++) {
    int ii = ord[i];
    int L = lower_bound(v.begin(), v.end(), x[ii] - r[ii]) - v.begin() + 1;
    int R = lower_bound(v.begin(), v.end(), x[ii] + r[ii]) - v.begin() + 1;
    get(L, ii);
    get(R, ii);
    if (ans[ii] == ii) {
      upd(L, R, ii);
    }
  }
  for (int i = 0; i < n; i++) printf("%d ", ans[i] + 1);
  printf("\n");
}
int main() {
  testCase();
  return 0;
}

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