oj.uz

Submission #895427

# Submission time Handle Problem Language Result Execution time Memory
895427 2023-12-29T23:53:51 Z MilosMilutinovic Circle selection (APIO18_circle_selection) C++14
37 / 100
 3000 ms 879036 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 4e6;

vector<pair<long long, int>> vec[N];
vector<int> qv;
vector<int> mn[N];
vector<int> mx[N];
vector<int> fa[N];
vector<bool> rem[N];

void Insert(int x, int l, int r, int i, pair<long long, int> v) {
  vec[x].push_back(v);
  if (l == r) {
    return;
  }
  int mid = l + r >> 1;
  if (i <= mid) {
    Insert(x << 1, l, mid, i, v);
  } else {
    Insert(x << 1 | 1, mid + 1, r, i, v);
  }
}

void Build(int x, int l, int r) {
  sort(vec[x].begin(), vec[x].end());
  int k = (int) vec[x].size();
  mn[x] = vector<int>(k);
  mx[x] = vector<int>(k);
  fa[x] = vector<int>(k);
  rem[x] = vector<bool>(k);
  iota(mn[x].begin(), mn[x].end(), 0);
  iota(mx[x].begin(), mx[x].end(), 0);
  iota(fa[x].begin(), fa[x].end(), 0);
  if (l == r) {
    return;
  }
  int mid = l + r >> 1;
  Build(x << 1, l, mid);
  Build(x << 1 | 1, mid + 1, r);
}

void Unite(int x, int a, int b) {
  a = fa[x][a];
  b = fa[x][b];
  if (a == b) {
    return;
  }
  if (mx[x][a] - mn[x][a] > mx[x][b] - mn[x][b]) {
    swap(a, b);
  }
  for (int i = mn[x][a]; i <= mx[x][a]; i++) {
    fa[x][i] = b;
  }
  mx[x][b] = max(mx[x][b], mx[x][a]);
  mn[x][b] = min(mn[x][b], mn[x][b]);
}

void Delete(int x, int l, int r, int i, pair<long long, int> v) {
  int idx = (int) (lower_bound(vec[x].begin(), vec[x].end(), v) - vec[x].begin());
  rem[x][idx] = true;
  if (idx > 0 && rem[x][idx - 1]) {
    Unite(x, idx - 1, idx);
  }
  if (idx + 1 < (int) vec[x].size() && rem[x][idx + 1]) {
    Unite(x, idx, idx + 1);
  }
  if (l == r) {
    return;
  }
  int mid = l + r >> 1;
  if (i <= mid) {
    Delete(x << 1, l, mid, i, v);
  } else {
    Delete(x << 1 | 1, mid + 1, r, i, v);
  }
}

void Query(int x, int l, int r, int ll, int rr, long long L, long long R) {
  if (ll <= l && r <= rr) {
    int idx = (int) (lower_bound(vec[x].begin(), vec[x].end(), make_pair(L, -1)) - vec[x].begin());
    while (idx < (int) vec[x].size() && vec[x][idx].first <= R) {
      if (rem[x][idx]) {
        idx = mx[x][fa[x][idx]] + 1;
        continue;
      }
      qv.push_back(vec[x][idx].second);
      idx += 1;
    }
    return;
  }
  int mid = l + r >> 1;
  if (rr <= mid) {
    Query(x << 1, l, mid, ll, rr, L, R);
  } else if (ll > mid) {
    Query(x << 1 | 1, mid + 1, r, ll, rr, L, R);
  } else {
    Query(x << 1, l, mid, ll, rr, L, R);
    Query(x << 1 | 1, mid + 1, r, ll, rr, L, R);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<long long> x(n), y(n), r(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i] >> r[i];
  }
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    if (r[i] != r[j]) {
      return r[i] > r[j];
    } else {
      return i < j;
    }
  });
  vector<long long> xs;
  for (int i = 0; i < n; i++) {
    xs.push_back(x[i] - 2 * r[i]);
    xs.push_back(x[i]);
    xs.push_back(x[i] + 2 * r[i]);
  }
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  int k = (int) xs.size();
  vector<int> res(n);
  for (int i = 0; i < n; i++) {
    res[i] = i;
    int p = (int) (lower_bound(xs.begin(), xs.end(), x[i]) - xs.begin());
    Insert(1, 0, k - 1, p, make_pair(y[i], i));
  }
  Build(1, 0, k - 1);
  for (int i : order) {
    if (res[i] != i) {
      continue;
    }
    qv.clear();
    int p = (int) (lower_bound(xs.begin(), xs.end(), x[i]) - xs.begin());
    Delete(1, 0, k - 1, p, make_pair(y[i], i));
    int L = (int) (lower_bound(xs.begin(), xs.end(), x[i] - 2 * r[i]) - xs.begin());
    int R = (int) (lower_bound(xs.begin(), xs.end(), x[i] + 2 * r[i]) - xs.begin());
    Query(1, 0, k - 1, L, R, y[i] - 2 * r[i], y[i] + 2 * r[i]);
    for (int j : qv) {
      if ((x[i] - x[j]) * 1LL * (x[i] - x[j]) + (y[i] - y[j]) * 1LL * (y[i] - y[j]) <= (r[i] + r[j]) * 1LL * (r[i] + r[j])) {
        res[j] = i;
        Delete(1, 0, k - 1, (int) (lower_bound(xs.begin(), xs.end(), x[j]) - xs.begin()), make_pair(y[j], j));
      }
    }
  }
  for (int i = 0; i < n; i++) {
    cout << res[i] + 1 << " ";
  }
  return 0;
}

Compilation message

circle_selection.cpp: In function 'void Insert(int, int, int, int, std::pair<long long int, int>)':
circle_selection.cpp:19:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |   int mid = l + r >> 1;
      |             ~~^~~
circle_selection.cpp: In function 'void Build(int, int, int)':
circle_selection.cpp:40:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |   int mid = l + r >> 1;
      |             ~~^~~
circle_selection.cpp: In function 'void Delete(int, int, int, int, std::pair<long long int, int>)':
circle_selection.cpp:73:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |   int mid = l + r >> 1;
      |             ~~^~~
circle_selection.cpp: In function 'void Query(int, int, int, int, int, long long int, long long int)':
circle_selection.cpp:94:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |   int mid = l + r >> 1;
      |             ~~^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 532556 KB Output is correct
2 Correct 110 ms 532564 KB Output is correct
3 Correct 110 ms 532560 KB Output is correct
4 Correct 112 ms 532816 KB Output is correct
5 Correct 110 ms 532680 KB Output is correct
6 Correct 112 ms 532684 KB Output is correct
7 Correct 110 ms 532560 KB Output is correct
8 Correct 111 ms 532568 KB Output is correct
9 Correct 112 ms 532684 KB Output is correct
10 Correct 110 ms 532564 KB Output is correct
11 Correct 111 ms 532612 KB Output is correct
12 Correct 110 ms 532816 KB Output is correct
13 Correct 110 ms 532560 KB Output is correct
14 Correct 110 ms 532652 KB Output is correct
15 Correct 115 ms 532704 KB Output is correct
16 Correct 119 ms 533584 KB Output is correct
17 Correct 117 ms 533332 KB Output is correct
18 Correct 113 ms 533328 KB Output is correct
19 Correct 129 ms 536528 KB Output is correct
20 Correct 127 ms 536404 KB Output is correct
21 Correct 129 ms 536372 KB Output is correct
22 Correct 135 ms 537428 KB Output is correct
23 Correct 136 ms 537288 KB Output is correct
24 Correct 144 ms 537700 KB Output is correct
25 Correct 134 ms 537412 KB Output is correct
26 Correct 135 ms 537424 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2582 ms 854168 KB Output is correct
2 Correct 2626 ms 851424 KB Output is correct
3 Correct 2577 ms 847840 KB Output is correct
4 Correct 2521 ms 839420 KB Output is correct
5 Correct 2550 ms 805884 KB Output is correct
6 Execution timed out 3047 ms 879036 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 532568 KB Output is correct
2 Correct 1392 ms 636888 KB Output is correct
3 Execution timed out 3068 ms 875976 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3030 ms 876280 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 532556 KB Output is correct
2 Correct 110 ms 532564 KB Output is correct
3 Correct 110 ms 532560 KB Output is correct
4 Correct 112 ms 532816 KB Output is correct
5 Correct 110 ms 532680 KB Output is correct
6 Correct 112 ms 532684 KB Output is correct
7 Correct 110 ms 532560 KB Output is correct
8 Correct 111 ms 532568 KB Output is correct
9 Correct 112 ms 532684 KB Output is correct
10 Correct 110 ms 532564 KB Output is correct
11 Correct 111 ms 532612 KB Output is correct
12 Correct 110 ms 532816 KB Output is correct
13 Correct 110 ms 532560 KB Output is correct
14 Correct 110 ms 532652 KB Output is correct
15 Correct 115 ms 532704 KB Output is correct
16 Correct 119 ms 533584 KB Output is correct
17 Correct 117 ms 533332 KB Output is correct
18 Correct 113 ms 533328 KB Output is correct
19 Correct 129 ms 536528 KB Output is correct
20 Correct 127 ms 536404 KB Output is correct
21 Correct 129 ms 536372 KB Output is correct
22 Correct 135 ms 537428 KB Output is correct
23 Correct 136 ms 537288 KB Output is correct
24 Correct 144 ms 537700 KB Output is correct
25 Correct 134 ms 537412 KB Output is correct
26 Correct 135 ms 537424 KB Output is correct
27 Correct 149 ms 540884 KB Output is correct
28 Correct 156 ms 541136 KB Output is correct
29 Correct 154 ms 541132 KB Output is correct
30 Correct 172 ms 542408 KB Output is correct
31 Correct 167 ms 542364 KB Output is correct
32 Correct 167 ms 542396 KB Output is correct
33 Correct 821 ms 622936 KB Output is correct
34 Correct 834 ms 627604 KB Output is correct
35 Correct 900 ms 634308 KB Output is correct
36 Correct 1360 ms 636340 KB Output is correct
37 Correct 1342 ms 638404 KB Output is correct
38 Correct 1338 ms 636608 KB Output is correct
39 Correct 613 ms 573908 KB Output is correct
40 Correct 586 ms 574228 KB Output is correct
41 Correct 614 ms 573928 KB Output is correct
42 Correct 538 ms 579936 KB Output is correct
43 Correct 1260 ms 639672 KB Output is correct
44 Correct 1261 ms 640488 KB Output is correct
45 Correct 1285 ms 640416 KB Output is correct
46 Correct 1263 ms 640720 KB Output is correct
47 Correct 1295 ms 640840 KB Output is correct
48 Correct 1251 ms 639816 KB Output is correct
49 Correct 1300 ms 641220 KB Output is correct
50 Correct 1271 ms 639888 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 532556 KB Output is correct
2 Correct 110 ms 532564 KB Output is correct
3 Correct 110 ms 532560 KB Output is correct
4 Correct 112 ms 532816 KB Output is correct
5 Correct 110 ms 532680 KB Output is correct
6 Correct 112 ms 532684 KB Output is correct
7 Correct 110 ms 532560 KB Output is correct
8 Correct 111 ms 532568 KB Output is correct
9 Correct 112 ms 532684 KB Output is correct
10 Correct 110 ms 532564 KB Output is correct
11 Correct 111 ms 532612 KB Output is correct
12 Correct 110 ms 532816 KB Output is correct
13 Correct 110 ms 532560 KB Output is correct
14 Correct 110 ms 532652 KB Output is correct
15 Correct 115 ms 532704 KB Output is correct
16 Correct 119 ms 533584 KB Output is correct
17 Correct 117 ms 533332 KB Output is correct
18 Correct 113 ms 533328 KB Output is correct
19 Correct 129 ms 536528 KB Output is correct
20 Correct 127 ms 536404 KB Output is correct
21 Correct 129 ms 536372 KB Output is correct
22 Correct 135 ms 537428 KB Output is correct
23 Correct 136 ms 537288 KB Output is correct
24 Correct 144 ms 537700 KB Output is correct
25 Correct 134 ms 537412 KB Output is correct
26 Correct 135 ms 537424 KB Output is correct
27 Correct 2582 ms 854168 KB Output is correct
28 Correct 2626 ms 851424 KB Output is correct
29 Correct 2577 ms 847840 KB Output is correct
30 Correct 2521 ms 839420 KB Output is correct
31 Correct 2550 ms 805884 KB Output is correct
32 Execution timed out 3047 ms 879036 KB Time limit exceeded
33 Halted 0 ms 0 KB -