oj.uz

Submission #966644

# Submission time Handle Problem Language Result Execution time Memory
966644 2024-04-20T07:37:39 Z Soumya1 Circle selection (APIO18_circle_selection) C++17
0 / 100
 573 ms 141492 KB 
#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[4 * mxN];
void update(int x, int lx, int rx, int l, int r, int i) {
  if (l > rx || lx > r) return;
  if (l <= lx && r >= rx) {
    st[x].insert({y[i], i});
    return;
  }
  int mx = (lx + rx) >> 1;
  update(x << 1, lx, mx, l, r, i);
  update(x << 1 | 1, mx + 1, rx, l, r, i);
}
bool intersect(int a, int b) {
  return 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]);
}
void update(int a, int b) {
  if (!intersect(a, b)) return;
  if (pos[b] < pos[ans[a]]) 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});
  int cnt = 5;
  while (it != st[x].end()) {
    if (i == 4) cout << (*it).second << endl;
    update(i, (*it).second);
    cnt--;
    it++;
    if (!cnt) break;
  }
  it = lower_bound(st[x].begin(), st[x].end(), pair<int, int> {y[i], -2e9});
  if (it == st[x].begin()) return;
  --it;
  cnt = 5;
  while (true) {
    update(i, (*it).second);
    if (it == st[x].begin()) break;
    cnt--;
    it--;
    if (!cnt) break;
  }
}
void query(int x, int lx, int rx, int p, int i) {
  check(x, i);
  if (lx == rx) return;
  int mx = (lx + rx) >> 1;
  if (p <= mx) query(x << 1, lx, mx, p, i);
  else query(x << 1 | 1, mx + 1, rx, p, i);
}
void testCase() {
  int n;
  cin >> n;
  vector<int> all;
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i] >> r[i];
    all.push_back(x[i] - r[i]);
    all.push_back(x[i] + r[i]); 
  }
  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;
  }
  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());
  int N = all.size();
  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(all.begin(), all.end(), x[ii] - r[ii]) - all.begin() + 1;
    int R = lower_bound(all.begin(), all.end(), x[ii] + r[ii]) - all.begin() + 1;
    query(1, 1, N, L, ii);
    query(1, 1, N, R, ii);
    if (ans[ii] == ii) {
      update(1, 1, N, L, R, ii);
    }
  }
  for (int i = 0; i < n; i++) cout << ans[i] + 1 << " ";
  cout << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 62044 KB Output is correct
2 Correct 12 ms 62056 KB Output is correct
3 Correct 12 ms 62044 KB Output is correct
4 Correct 13 ms 62092 KB Output is correct
5 Incorrect 13 ms 62040 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 237 ms 140588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 62040 KB Output is correct
2 Incorrect 573 ms 89304 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 189 ms 141492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 62044 KB Output is correct
2 Correct 12 ms 62056 KB Output is correct
3 Correct 12 ms 62044 KB Output is correct
4 Correct 13 ms 62092 KB Output is correct
5 Incorrect 13 ms 62040 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 62044 KB Output is correct
2 Correct 12 ms 62056 KB Output is correct
3 Correct 12 ms 62044 KB Output is correct
4 Correct 13 ms 62092 KB Output is correct
5 Incorrect 13 ms 62040 KB Output isn't correct
6 Halted 0 ms 0 KB -