oj.uz

Submission #966675

# Submission time Handle Problem Language Result Execution time Memory
966675 2024-04-20T08:06:48 Z Soumya1 Circle selection (APIO18_circle_selection) C++17
49 / 100
 3000 ms 197404 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];
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> all;
  for (int i = 0; i < n; i++) {
    rf(x[i]), rf(y[i]), rf(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 (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(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;
    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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 117484 KB Output is correct
2 Correct 25 ms 117336 KB Output is correct
3 Correct 25 ms 117340 KB Output is correct
4 Correct 26 ms 117336 KB Output is correct
5 Correct 27 ms 117596 KB Output is correct
6 Correct 24 ms 117340 KB Output is correct
7 Correct 25 ms 117824 KB Output is correct
8 Correct 25 ms 117444 KB Output is correct
9 Correct 24 ms 117340 KB Output is correct
10 Correct 24 ms 117340 KB Output is correct
11 Correct 26 ms 117596 KB Output is correct
12 Correct 24 ms 117540 KB Output is correct
13 Correct 26 ms 117572 KB Output is correct
14 Correct 24 ms 117472 KB Output is correct
15 Correct 24 ms 117596 KB Output is correct
16 Correct 26 ms 117588 KB Output is correct
17 Correct 24 ms 117592 KB Output is correct
18 Correct 25 ms 117596 KB Output is correct
19 Correct 29 ms 117844 KB Output is correct
20 Correct 28 ms 117852 KB Output is correct
21 Correct 29 ms 117720 KB Output is correct
22 Correct 30 ms 118316 KB Output is correct
23 Correct 40 ms 118760 KB Output is correct
24 Correct 30 ms 118100 KB Output is correct
25 Correct 29 ms 117940 KB Output is correct
26 Correct 29 ms 118076 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 132276 KB Output is correct
2 Correct 680 ms 131512 KB Output is correct
3 Correct 653 ms 130744 KB Output is correct
4 Correct 633 ms 130388 KB Output is correct
5 Correct 531 ms 130424 KB Output is correct
6 Correct 578 ms 139368 KB Output is correct
7 Correct 608 ms 131988 KB Output is correct
8 Correct 594 ms 133300 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 117584 KB Output is correct
2 Correct 462 ms 144068 KB Output is correct
3 Correct 1816 ms 196748 KB Output is correct
4 Correct 1755 ms 197404 KB Output is correct
5 Execution timed out 3020 ms 192224 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1211 ms 186920 KB Output is correct
2 Correct 554 ms 151304 KB Output is correct
3 Execution timed out 3096 ms 135300 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 117484 KB Output is correct
2 Correct 25 ms 117336 KB Output is correct
3 Correct 25 ms 117340 KB Output is correct
4 Correct 26 ms 117336 KB Output is correct
5 Correct 27 ms 117596 KB Output is correct
6 Correct 24 ms 117340 KB Output is correct
7 Correct 25 ms 117824 KB Output is correct
8 Correct 25 ms 117444 KB Output is correct
9 Correct 24 ms 117340 KB Output is correct
10 Correct 24 ms 117340 KB Output is correct
11 Correct 26 ms 117596 KB Output is correct
12 Correct 24 ms 117540 KB Output is correct
13 Correct 26 ms 117572 KB Output is correct
14 Correct 24 ms 117472 KB Output is correct
15 Correct 24 ms 117596 KB Output is correct
16 Correct 26 ms 117588 KB Output is correct
17 Correct 24 ms 117592 KB Output is correct
18 Correct 25 ms 117596 KB Output is correct
19 Correct 29 ms 117844 KB Output is correct
20 Correct 28 ms 117852 KB Output is correct
21 Correct 29 ms 117720 KB Output is correct
22 Correct 30 ms 118316 KB Output is correct
23 Correct 40 ms 118760 KB Output is correct
24 Correct 30 ms 118100 KB Output is correct
25 Correct 29 ms 117940 KB Output is correct
26 Correct 29 ms 118076 KB Output is correct
27 Correct 52 ms 118076 KB Output is correct
28 Correct 38 ms 118100 KB Output is correct
29 Correct 38 ms 118140 KB Output is correct
30 Correct 47 ms 119800 KB Output is correct
31 Correct 40 ms 118892 KB Output is correct
32 Correct 39 ms 118840 KB Output is correct
33 Correct 159 ms 121440 KB Output is correct
34 Correct 184 ms 121544 KB Output is correct
35 Correct 201 ms 121492 KB Output is correct
36 Correct 279 ms 133932 KB Output is correct
37 Correct 244 ms 134368 KB Output is correct
38 Correct 290 ms 136468 KB Output is correct
39 Correct 1084 ms 122648 KB Output is correct
40 Correct 1042 ms 122792 KB Output is correct
41 Correct 1010 ms 122644 KB Output is correct
42 Correct 689 ms 123612 KB Output is correct
43 Correct 186 ms 126660 KB Output is correct
44 Correct 153 ms 125888 KB Output is correct
45 Correct 161 ms 126580 KB Output is correct
46 Correct 154 ms 126404 KB Output is correct
47 Correct 150 ms 125480 KB Output is correct
48 Correct 152 ms 126456 KB Output is correct
49 Correct 146 ms 125132 KB Output is correct
50 Correct 157 ms 127428 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 117484 KB Output is correct
2 Correct 25 ms 117336 KB Output is correct
3 Correct 25 ms 117340 KB Output is correct
4 Correct 26 ms 117336 KB Output is correct
5 Correct 27 ms 117596 KB Output is correct
6 Correct 24 ms 117340 KB Output is correct
7 Correct 25 ms 117824 KB Output is correct
8 Correct 25 ms 117444 KB Output is correct
9 Correct 24 ms 117340 KB Output is correct
10 Correct 24 ms 117340 KB Output is correct
11 Correct 26 ms 117596 KB Output is correct
12 Correct 24 ms 117540 KB Output is correct
13 Correct 26 ms 117572 KB Output is correct
14 Correct 24 ms 117472 KB Output is correct
15 Correct 24 ms 117596 KB Output is correct
16 Correct 26 ms 117588 KB Output is correct
17 Correct 24 ms 117592 KB Output is correct
18 Correct 25 ms 117596 KB Output is correct
19 Correct 29 ms 117844 KB Output is correct
20 Correct 28 ms 117852 KB Output is correct
21 Correct 29 ms 117720 KB Output is correct
22 Correct 30 ms 118316 KB Output is correct
23 Correct 40 ms 118760 KB Output is correct
24 Correct 30 ms 118100 KB Output is correct
25 Correct 29 ms 117940 KB Output is correct
26 Correct 29 ms 118076 KB Output is correct
27 Correct 630 ms 132276 KB Output is correct
28 Correct 680 ms 131512 KB Output is correct
29 Correct 653 ms 130744 KB Output is correct
30 Correct 633 ms 130388 KB Output is correct
31 Correct 531 ms 130424 KB Output is correct
32 Correct 578 ms 139368 KB Output is correct
33 Correct 608 ms 131988 KB Output is correct
34 Correct 594 ms 133300 KB Output is correct
35 Correct 25 ms 117584 KB Output is correct
36 Correct 462 ms 144068 KB Output is correct
37 Correct 1816 ms 196748 KB Output is correct
38 Correct 1755 ms 197404 KB Output is correct
39 Execution timed out 3020 ms 192224 KB Time limit exceeded
40 Halted 0 ms 0 KB -