oj.uz

Submission #966664

# Submission time Handle Problem Language Result Execution time Memory
966664 2024-04-20T07:54:02 Z Soumya1 Circle selection (APIO18_circle_selection) C++17
72 / 100
 3000 ms 200216 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[2 * 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});
  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 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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 117476 KB Output is correct
2 Correct 26 ms 117568 KB Output is correct
3 Correct 27 ms 117584 KB Output is correct
4 Correct 26 ms 117332 KB Output is correct
5 Correct 28 ms 117596 KB Output is correct
6 Correct 25 ms 117592 KB Output is correct
7 Correct 24 ms 117332 KB Output is correct
8 Correct 24 ms 117596 KB Output is correct
9 Correct 24 ms 117612 KB Output is correct
10 Correct 24 ms 117584 KB Output is correct
11 Correct 25 ms 117596 KB Output is correct
12 Correct 24 ms 117616 KB Output is correct
13 Correct 53 ms 117596 KB Output is correct
14 Correct 25 ms 117596 KB Output is correct
15 Correct 25 ms 117544 KB Output is correct
16 Correct 25 ms 117848 KB Output is correct
17 Correct 27 ms 117596 KB Output is correct
18 Correct 25 ms 117596 KB Output is correct
19 Correct 30 ms 117852 KB Output is correct
20 Correct 29 ms 117876 KB Output is correct
21 Correct 32 ms 117700 KB Output is correct
22 Correct 32 ms 118364 KB Output is correct
23 Correct 38 ms 118860 KB Output is correct
24 Correct 32 ms 118112 KB Output is correct
25 Correct 31 ms 118096 KB Output is correct
26 Correct 31 ms 118096 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 669 ms 132108 KB Output is correct
2 Correct 712 ms 133060 KB Output is correct
3 Correct 716 ms 132540 KB Output is correct
4 Correct 783 ms 133060 KB Output is correct
5 Correct 573 ms 130136 KB Output is correct
6 Correct 732 ms 141840 KB Output is correct
7 Correct 661 ms 131796 KB Output is correct
8 Correct 670 ms 135792 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 117480 KB Output is correct
2 Correct 510 ms 145124 KB Output is correct
3 Correct 1953 ms 199684 KB Output is correct
4 Correct 1884 ms 200216 KB Output is correct
5 Execution timed out 3017 ms 196308 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1200 ms 191220 KB Output is correct
2 Correct 596 ms 154216 KB Output is correct
3 Correct 2695 ms 140856 KB Output is correct
4 Correct 670 ms 158588 KB Output is correct
5 Correct 640 ms 157772 KB Output is correct
6 Correct 2187 ms 135168 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 117476 KB Output is correct
2 Correct 26 ms 117568 KB Output is correct
3 Correct 27 ms 117584 KB Output is correct
4 Correct 26 ms 117332 KB Output is correct
5 Correct 28 ms 117596 KB Output is correct
6 Correct 25 ms 117592 KB Output is correct
7 Correct 24 ms 117332 KB Output is correct
8 Correct 24 ms 117596 KB Output is correct
9 Correct 24 ms 117612 KB Output is correct
10 Correct 24 ms 117584 KB Output is correct
11 Correct 25 ms 117596 KB Output is correct
12 Correct 24 ms 117616 KB Output is correct
13 Correct 53 ms 117596 KB Output is correct
14 Correct 25 ms 117596 KB Output is correct
15 Correct 25 ms 117544 KB Output is correct
16 Correct 25 ms 117848 KB Output is correct
17 Correct 27 ms 117596 KB Output is correct
18 Correct 25 ms 117596 KB Output is correct
19 Correct 30 ms 117852 KB Output is correct
20 Correct 29 ms 117876 KB Output is correct
21 Correct 32 ms 117700 KB Output is correct
22 Correct 32 ms 118364 KB Output is correct
23 Correct 38 ms 118860 KB Output is correct
24 Correct 32 ms 118112 KB Output is correct
25 Correct 31 ms 118096 KB Output is correct
26 Correct 31 ms 118096 KB Output is correct
27 Correct 37 ms 118160 KB Output is correct
28 Correct 46 ms 118100 KB Output is correct
29 Correct 42 ms 118360 KB Output is correct
30 Correct 44 ms 119888 KB Output is correct
31 Correct 40 ms 119076 KB Output is correct
32 Correct 39 ms 119124 KB Output is correct
33 Correct 170 ms 122832 KB Output is correct
34 Correct 182 ms 122828 KB Output is correct
35 Correct 243 ms 122620 KB Output is correct
36 Correct 270 ms 135632 KB Output is correct
37 Correct 278 ms 135876 KB Output is correct
38 Correct 320 ms 137936 KB Output is correct
39 Correct 1033 ms 123872 KB Output is correct
40 Correct 1033 ms 123896 KB Output is correct
41 Correct 1032 ms 124020 KB Output is correct
42 Correct 692 ms 124520 KB Output is correct
43 Correct 194 ms 129440 KB Output is correct
44 Correct 200 ms 129616 KB Output is correct
45 Correct 199 ms 129484 KB Output is correct
46 Correct 198 ms 129484 KB Output is correct
47 Correct 206 ms 129600 KB Output is correct
48 Correct 193 ms 129432 KB Output is correct
49 Correct 191 ms 129492 KB Output is correct
50 Correct 194 ms 129772 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 117476 KB Output is correct
2 Correct 26 ms 117568 KB Output is correct
3 Correct 27 ms 117584 KB Output is correct
4 Correct 26 ms 117332 KB Output is correct
5 Correct 28 ms 117596 KB Output is correct
6 Correct 25 ms 117592 KB Output is correct
7 Correct 24 ms 117332 KB Output is correct
8 Correct 24 ms 117596 KB Output is correct
9 Correct 24 ms 117612 KB Output is correct
10 Correct 24 ms 117584 KB Output is correct
11 Correct 25 ms 117596 KB Output is correct
12 Correct 24 ms 117616 KB Output is correct
13 Correct 53 ms 117596 KB Output is correct
14 Correct 25 ms 117596 KB Output is correct
15 Correct 25 ms 117544 KB Output is correct
16 Correct 25 ms 117848 KB Output is correct
17 Correct 27 ms 117596 KB Output is correct
18 Correct 25 ms 117596 KB Output is correct
19 Correct 30 ms 117852 KB Output is correct
20 Correct 29 ms 117876 KB Output is correct
21 Correct 32 ms 117700 KB Output is correct
22 Correct 32 ms 118364 KB Output is correct
23 Correct 38 ms 118860 KB Output is correct
24 Correct 32 ms 118112 KB Output is correct
25 Correct 31 ms 118096 KB Output is correct
26 Correct 31 ms 118096 KB Output is correct
27 Correct 669 ms 132108 KB Output is correct
28 Correct 712 ms 133060 KB Output is correct
29 Correct 716 ms 132540 KB Output is correct
30 Correct 783 ms 133060 KB Output is correct
31 Correct 573 ms 130136 KB Output is correct
32 Correct 732 ms 141840 KB Output is correct
33 Correct 661 ms 131796 KB Output is correct
34 Correct 670 ms 135792 KB Output is correct
35 Correct 23 ms 117480 KB Output is correct
36 Correct 510 ms 145124 KB Output is correct
37 Correct 1953 ms 199684 KB Output is correct
38 Correct 1884 ms 200216 KB Output is correct
39 Execution timed out 3017 ms 196308 KB Time limit exceeded
40 Halted 0 ms 0 KB -