oj.uz

Submission #966628

# Submission time Handle Problem Language Result Execution time Memory
966628 2024-04-20T07:15:08 Z Soumya1 Circle selection (APIO18_circle_selection) C++17
0 / 100
 520 ms 136076 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 = 5000;
  while (it != st[x].end()) {
    update(i, (*it).second);
    cnt--;
    it++;
    if (!cnt) break;
  }
  it = lower_bound(st[x].begin(), st[x].end(), pair<int, int> {y[i], -2e9});
  cnt = 5000;
  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 15 ms 62296 KB Output is correct
2 Correct 12 ms 62044 KB Output is correct
3 Correct 12 ms 62376 KB Output is correct
4 Correct 12 ms 62044 KB Output is correct
5 Correct 12 ms 62044 KB Output is correct
6 Correct 12 ms 62044 KB Output is correct
7 Correct 13 ms 62044 KB Output is correct
8 Correct 13 ms 62044 KB Output is correct
9 Correct 13 ms 62044 KB Output is correct
10 Correct 13 ms 62044 KB Output is correct
11 Correct 13 ms 62040 KB Output is correct
12 Correct 14 ms 62040 KB Output is correct
13 Correct 13 ms 62044 KB Output is correct
14 Correct 12 ms 62044 KB Output is correct
15 Correct 13 ms 62044 KB Output is correct
16 Correct 14 ms 62212 KB Output is correct
17 Correct 13 ms 62040 KB Output is correct
18 Correct 14 ms 62044 KB Output is correct
19 Correct 19 ms 62556 KB Output is correct
20 Correct 20 ms 62300 KB Output is correct
21 Incorrect 20 ms 62300 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 199 ms 136064 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 62044 KB Output is correct
2 Correct 520 ms 86580 KB Output is correct
3 Runtime error 203 ms 136076 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 172 ms 133820 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 15 ms 62296 KB Output is correct
2 Correct 12 ms 62044 KB Output is correct
3 Correct 12 ms 62376 KB Output is correct
4 Correct 12 ms 62044 KB Output is correct
5 Correct 12 ms 62044 KB Output is correct
6 Correct 12 ms 62044 KB Output is correct
7 Correct 13 ms 62044 KB Output is correct
8 Correct 13 ms 62044 KB Output is correct
9 Correct 13 ms 62044 KB Output is correct
10 Correct 13 ms 62044 KB Output is correct
11 Correct 13 ms 62040 KB Output is correct
12 Correct 14 ms 62040 KB Output is correct
13 Correct 13 ms 62044 KB Output is correct
14 Correct 12 ms 62044 KB Output is correct
15 Correct 13 ms 62044 KB Output is correct
16 Correct 14 ms 62212 KB Output is correct
17 Correct 13 ms 62040 KB Output is correct
18 Correct 14 ms 62044 KB Output is correct
19 Correct 19 ms 62556 KB Output is correct
20 Correct 20 ms 62300 KB Output is correct
21 Incorrect 20 ms 62300 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 62296 KB Output is correct
2 Correct 12 ms 62044 KB Output is correct
3 Correct 12 ms 62376 KB Output is correct
4 Correct 12 ms 62044 KB Output is correct
5 Correct 12 ms 62044 KB Output is correct
6 Correct 12 ms 62044 KB Output is correct
7 Correct 13 ms 62044 KB Output is correct
8 Correct 13 ms 62044 KB Output is correct
9 Correct 13 ms 62044 KB Output is correct
10 Correct 13 ms 62044 KB Output is correct
11 Correct 13 ms 62040 KB Output is correct
12 Correct 14 ms 62040 KB Output is correct
13 Correct 13 ms 62044 KB Output is correct
14 Correct 12 ms 62044 KB Output is correct
15 Correct 13 ms 62044 KB Output is correct
16 Correct 14 ms 62212 KB Output is correct
17 Correct 13 ms 62040 KB Output is correct
18 Correct 14 ms 62044 KB Output is correct
19 Correct 19 ms 62556 KB Output is correct
20 Correct 20 ms 62300 KB Output is correct
21 Incorrect 20 ms 62300 KB Output isn't correct
22 Halted 0 ms 0 KB -