제출 #829851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
829851		erdemkiraz	원 고르기 (APIO18_circle_selection)	C++17	87 / 100	3061 ms	55984 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

#define y1 ___y1

typedef long long ll;
typedef pair<ll, ll> pll;

const int inf = 1e9 + 333;
const ll linf = 1e18 + 333;

const int N = 3e5 + 5;

class tree {
public:
  ll x, y, x1, y1, x2, y2;
  int idx;
  int alive, sum;
  tree *l, *r;
  tree() {
    x = y = x1 = y1 = x2 = y2 = idx = -1;
    alive = sum = 0;
    l = r = 0;
  }
};

typedef tree *pTree;

int n, sz, type;
ll x1, y1, x2, y2;
ll k;
map<pll, int> h;
map<pll, ll> M;
pair<pll, int> a[N];

bool cmp(pair<pll, int> x, pair<pll, int> y) {
  if (x.first.second == y.first.second)
    return x.first.first < y.first.first;
  return x.first.second < y.first.second;
}

void init(pTree t, int l, int r, bool d = 0) {

  // printf("l = %d r = %d\n", l, r);

  int m = (l + r) >> 1;

  if (!d)
    nth_element(a + l, a + m, a + r + 1);
  else
    nth_element(a + l, a + m, a + r + 1, cmp);

  // puts("ASD");

  t->x = t->x1 = t->x2 = a[m].first.first;
  t->y = t->y1 = t->y2 = a[m].first.second;
  t->idx = a[m].second;
  t->alive = t->sum = 1;

  if (l < m) {
    if (!t->l)
      t->l = new tree;
    init(t->l, l, m - 1, !d);
    t->sum += t->l->sum;
    t->x1 = min(t->x1, t->l->x1);
    t->y1 = min(t->y1, t->l->y1);
    t->x2 = max(t->x2, t->l->x2);
    t->y2 = max(t->y2, t->l->y2);
  }

  if (m < r) {
    if (!t->r)
      t->r = new tree;
    init(t->r, m + 1, r, !d);
    t->sum += t->r->sum;
    t->x1 = min(t->x1, t->r->x1);
    t->y1 = min(t->y1, t->r->y1);
    t->x2 = max(t->x2, t->r->x2);
    t->y2 = max(t->y2, t->r->y2);
  }
}

ll X[N], Y[N], R[N];
int ord[N], ans[N];

bool check_intersection(ll x1, ll y1, ll r1, ll x2, ll y2, ll r2) {
  return (ll) (x1 - x2) * (x1 - x2) + (ll) (y1 - y2) * (y1 - y2) <= (ll) (r1 + r2) * (r1 + r2);
}

ll ox, oy, o_r;
int oid;

void query(pTree t) {

  if (x2 < t->x1 or t->x2 < x1 or y2 < t->y1 or t->y2 < y1)
    return;

  // if (x1 <= t->x1 and t->x2 <= x2 and y1 <= t->y1 and t->y2 <= y2)
  //   return t->ans;

  if(t->alive and check_intersection(ox, oy, o_r, X[t->idx], Y[t->idx], R[t->idx])) {
    ans[t->idx] = oid;
    t->alive = 0;
  }

  if (t->l)
    query(t->l);

  if (t->r)
    query(t->r);

  t->sum = (t->l?t->l->sum:0) + (t->r?t->r->sum:0) + t->alive;
}

// void change(pTree t, bool d = 0) {

//   if (x1 == t->x and y1 == t->y) {
//     t->val = t->ans = k;
//     if (t->l)
//       t->ans = gcd(t->ans, t->l->ans);
//     if (t->r)
//       t->ans = gcd(t->ans, t->r->ans);
//     return;
//   }

//   if ((!d and pll(x1, y1) < pll(t->x, t->y)) or (d and pll(y1, x1) < pll(t->y, t->x)))
//     change(t->l, !d);
//   else
//     change(t->r, !d);

//   t->ans = t->val;

//   if (t->l)
//     t->ans = gcd(t->ans, t->l->ans);

//   if (t->r)
//     t->ans = gcd(t->ans, t->r->ans);
// }

pTree t;

void calculate(ll x, ll y, ll r, int id) {
  ::x1 = x - 2 * r;
  ::y1 = y - 2 * r;
  ::x2 = x + 2 * r;
  ::y2 = y + 2 * r;

  ox = x;
  oy = y;
  o_r = r;
  oid = id;

  query(t);
}

int main() {
  memset(ans, -1, sizeof(ans));

  t = new tree;

  scanf("%d", &n);

  for(int i = 0; i < n; i++) {
    scanf("%lld %lld %lld", X + i, Y + i, R + i);
    ord[i] = i;
    a[i] = {{X[i], Y[i]}, i};
  }
  sort(ord, ord + n, [&](int x, int y){
    if(R[x] != R[y]) {
      return R[x] > R[y];
    }
    return x < y;
  });

  // puts("ASD");

  init(t, 0, n - 1);

  // puts("BSD");

  for(int i = 0; i < n; i++) {
    ll x = X[ord[i]];
    ll y = Y[ord[i]];
    ll r = R[ord[i]];

    if(ans[ord[i]] != -1) {
      continue;
    }

    ans[ord[i]] = ord[i];

    calculate(x, y, r, ord[i]);
  }

  for(int i = 0; i < n; i++) {
    printf("%d ", ans[i] + 1);
  }
  puts("");
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:162:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
circle_selection.cpp:165:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |     scanf("%lld %lld %lld", X + i, Y + i, R + i);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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