oj.uz

Submission #966677

# Submission time Handle Problem Language Result Execution time Memory
966677 2024-04-20T08:09:44 Z Soumya1 Circle selection (APIO18_circle_selection) C++17
72 / 100
 3000 ms 202128 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> vx, vy;
  for (int i = 0; i < n; i++) {
    rf(x[i]), rf(y[i]), rf(r[i]);
    vx.push_back(x[i] - r[i]);
    vx.push_back(x[i] + r[i]); 
    vy.push_back(y[i] - r[i]);
    vy.push_back(y[i] + r[i]); 
  }
  sort(vx.begin(), vx.end());
  vx.erase(unique(vx.begin(), vx.end()), vx.end());
  sort(vy.begin(), vy.end());
  vy.erase(unique(vy.begin(), vy.end()), vy.end());
  vector<int> v;
  if (vx.size() < vy.size()) {
    for (int i = 0; i < n; i++) swap(x[i], y[i]);
    v = vy;
  } else {
    v = vx;
  }
  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;
  }
  int N = v.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(v.begin(), v.end(), x[ii] - r[ii]) - v.begin() + 1;
    int R = lower_bound(v.begin(), v.end(), x[ii] + r[ii]) - v.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 64 ms 117336 KB Output is correct
2 Correct 29 ms 117636 KB Output is correct
3 Correct 24 ms 117340 KB Output is correct
4 Correct 24 ms 117336 KB Output is correct
5 Correct 24 ms 117340 KB Output is correct
6 Correct 25 ms 117340 KB Output is correct
7 Correct 24 ms 117336 KB Output is correct
8 Correct 23 ms 117340 KB Output is correct
9 Correct 24 ms 117340 KB Output is correct
10 Correct 26 ms 117588 KB Output is correct
11 Correct 25 ms 117616 KB Output is correct
12 Correct 24 ms 117596 KB Output is correct
13 Correct 24 ms 117340 KB Output is correct
14 Correct 25 ms 117340 KB Output is correct
15 Correct 24 ms 117340 KB Output is correct
16 Correct 25 ms 117444 KB Output is correct
17 Correct 26 ms 117588 KB Output is correct
18 Correct 24 ms 117464 KB Output is correct
19 Correct 30 ms 117928 KB Output is correct
20 Correct 29 ms 117840 KB Output is correct
21 Correct 30 ms 117816 KB Output is correct
22 Correct 30 ms 118100 KB Output is correct
23 Correct 29 ms 118080 KB Output is correct
24 Correct 31 ms 118364 KB Output is correct
25 Correct 30 ms 118100 KB Output is correct
26 Correct 31 ms 118108 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 134928 KB Output is correct
2 Correct 699 ms 134812 KB Output is correct
3 Correct 693 ms 134136 KB Output is correct
4 Correct 689 ms 134284 KB Output is correct
5 Correct 561 ms 133832 KB Output is correct
6 Correct 612 ms 143924 KB Output is correct
7 Correct 624 ms 135832 KB Output is correct
8 Correct 643 ms 138632 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 117340 KB Output is correct
2 Correct 462 ms 145336 KB Output is correct
3 Correct 1818 ms 202128 KB Output is correct
4 Correct 1850 ms 200852 KB Output is correct
5 Execution timed out 3097 ms 195112 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 987 ms 184220 KB Output is correct
2 Correct 519 ms 154788 KB Output is correct
3 Correct 2724 ms 142456 KB Output is correct
4 Correct 546 ms 160264 KB Output is correct
5 Correct 554 ms 159252 KB Output is correct
6 Correct 1238 ms 139528 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 117336 KB Output is correct
2 Correct 29 ms 117636 KB Output is correct
3 Correct 24 ms 117340 KB Output is correct
4 Correct 24 ms 117336 KB Output is correct
5 Correct 24 ms 117340 KB Output is correct
6 Correct 25 ms 117340 KB Output is correct
7 Correct 24 ms 117336 KB Output is correct
8 Correct 23 ms 117340 KB Output is correct
9 Correct 24 ms 117340 KB Output is correct
10 Correct 26 ms 117588 KB Output is correct
11 Correct 25 ms 117616 KB Output is correct
12 Correct 24 ms 117596 KB Output is correct
13 Correct 24 ms 117340 KB Output is correct
14 Correct 25 ms 117340 KB Output is correct
15 Correct 24 ms 117340 KB Output is correct
16 Correct 25 ms 117444 KB Output is correct
17 Correct 26 ms 117588 KB Output is correct
18 Correct 24 ms 117464 KB Output is correct
19 Correct 30 ms 117928 KB Output is correct
20 Correct 29 ms 117840 KB Output is correct
21 Correct 30 ms 117816 KB Output is correct
22 Correct 30 ms 118100 KB Output is correct
23 Correct 29 ms 118080 KB Output is correct
24 Correct 31 ms 118364 KB Output is correct
25 Correct 30 ms 118100 KB Output is correct
26 Correct 31 ms 118108 KB Output is correct
27 Correct 35 ms 118232 KB Output is correct
28 Correct 36 ms 118108 KB Output is correct
29 Correct 34 ms 118232 KB Output is correct
30 Correct 36 ms 118748 KB Output is correct
31 Correct 37 ms 119132 KB Output is correct
32 Correct 37 ms 119124 KB Output is correct
33 Correct 159 ms 123332 KB Output is correct
34 Correct 174 ms 123332 KB Output is correct
35 Correct 191 ms 123024 KB Output is correct
36 Correct 237 ms 135632 KB Output is correct
37 Correct 212 ms 134088 KB Output is correct
38 Correct 274 ms 138436 KB Output is correct
39 Correct 1037 ms 124352 KB Output is correct
40 Correct 1020 ms 124236 KB Output is correct
41 Correct 1074 ms 124300 KB Output is correct
42 Correct 660 ms 124600 KB Output is correct
43 Correct 164 ms 129936 KB Output is correct
44 Correct 164 ms 129724 KB Output is correct
45 Correct 170 ms 129580 KB Output is correct
46 Correct 163 ms 128704 KB Output is correct
47 Correct 162 ms 128444 KB Output is correct
48 Correct 160 ms 129468 KB Output is correct
49 Correct 162 ms 128700 KB Output is correct
50 Correct 163 ms 127508 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 117336 KB Output is correct
2 Correct 29 ms 117636 KB Output is correct
3 Correct 24 ms 117340 KB Output is correct
4 Correct 24 ms 117336 KB Output is correct
5 Correct 24 ms 117340 KB Output is correct
6 Correct 25 ms 117340 KB Output is correct
7 Correct 24 ms 117336 KB Output is correct
8 Correct 23 ms 117340 KB Output is correct
9 Correct 24 ms 117340 KB Output is correct
10 Correct 26 ms 117588 KB Output is correct
11 Correct 25 ms 117616 KB Output is correct
12 Correct 24 ms 117596 KB Output is correct
13 Correct 24 ms 117340 KB Output is correct
14 Correct 25 ms 117340 KB Output is correct
15 Correct 24 ms 117340 KB Output is correct
16 Correct 25 ms 117444 KB Output is correct
17 Correct 26 ms 117588 KB Output is correct
18 Correct 24 ms 117464 KB Output is correct
19 Correct 30 ms 117928 KB Output is correct
20 Correct 29 ms 117840 KB Output is correct
21 Correct 30 ms 117816 KB Output is correct
22 Correct 30 ms 118100 KB Output is correct
23 Correct 29 ms 118080 KB Output is correct
24 Correct 31 ms 118364 KB Output is correct
25 Correct 30 ms 118100 KB Output is correct
26 Correct 31 ms 118108 KB Output is correct
27 Correct 705 ms 134928 KB Output is correct
28 Correct 699 ms 134812 KB Output is correct
29 Correct 693 ms 134136 KB Output is correct
30 Correct 689 ms 134284 KB Output is correct
31 Correct 561 ms 133832 KB Output is correct
32 Correct 612 ms 143924 KB Output is correct
33 Correct 624 ms 135832 KB Output is correct
34 Correct 643 ms 138632 KB Output is correct
35 Correct 24 ms 117340 KB Output is correct
36 Correct 462 ms 145336 KB Output is correct
37 Correct 1818 ms 202128 KB Output is correct
38 Correct 1850 ms 200852 KB Output is correct
39 Execution timed out 3097 ms 195112 KB Time limit exceeded
40 Halted 0 ms 0 KB -