oj.uz

Submission #895428

# Submission time Handle Problem Language Result Execution time Memory
895428 2023-12-29T23:54:47 Z MilosMilutinovic Circle selection (APIO18_circle_selection) C++17
37 / 100
 3000 ms 883880 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 116 ms 532720 KB Output is correct
2 Correct 111 ms 532808 KB Output is correct
3 Correct 111 ms 532564 KB Output is correct
4 Correct 110 ms 532560 KB Output is correct
5 Correct 113 ms 532564 KB Output is correct
6 Correct 113 ms 532616 KB Output is correct
7 Correct 112 ms 532560 KB Output is correct
8 Correct 110 ms 532560 KB Output is correct
9 Correct 110 ms 532564 KB Output is correct
10 Correct 110 ms 532692 KB Output is correct
11 Correct 114 ms 532996 KB Output is correct
12 Correct 111 ms 532564 KB Output is correct
13 Correct 111 ms 532564 KB Output is correct
14 Correct 113 ms 532564 KB Output is correct
15 Correct 112 ms 532816 KB Output is correct
16 Correct 114 ms 533452 KB Output is correct
17 Correct 115 ms 533324 KB Output is correct
18 Correct 116 ms 533332 KB Output is correct
19 Correct 132 ms 536576 KB Output is correct
20 Correct 128 ms 536244 KB Output is correct
21 Correct 127 ms 536400 KB Output is correct
22 Correct 135 ms 537400 KB Output is correct
23 Correct 142 ms 537408 KB Output is correct
24 Correct 135 ms 537508 KB Output is correct
25 Correct 136 ms 537428 KB Output is correct
26 Correct 135 ms 537456 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2420 ms 856248 KB Output is correct
2 Correct 2514 ms 850440 KB Output is correct
3 Correct 2466 ms 849160 KB Output is correct
4 Correct 2449 ms 839972 KB Output is correct
5 Correct 2400 ms 806364 KB Output is correct
6 Execution timed out 3024 ms 883880 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 532560 KB Output is correct
2 Correct 1331 ms 636100 KB Output is correct
3 Execution timed out 3075 ms 875316 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 3065 ms 873848 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 532720 KB Output is correct
2 Correct 111 ms 532808 KB Output is correct
3 Correct 111 ms 532564 KB Output is correct
4 Correct 110 ms 532560 KB Output is correct
5 Correct 113 ms 532564 KB Output is correct
6 Correct 113 ms 532616 KB Output is correct
7 Correct 112 ms 532560 KB Output is correct
8 Correct 110 ms 532560 KB Output is correct
9 Correct 110 ms 532564 KB Output is correct
10 Correct 110 ms 532692 KB Output is correct
11 Correct 114 ms 532996 KB Output is correct
12 Correct 111 ms 532564 KB Output is correct
13 Correct 111 ms 532564 KB Output is correct
14 Correct 113 ms 532564 KB Output is correct
15 Correct 112 ms 532816 KB Output is correct
16 Correct 114 ms 533452 KB Output is correct
17 Correct 115 ms 533324 KB Output is correct
18 Correct 116 ms 533332 KB Output is correct
19 Correct 132 ms 536576 KB Output is correct
20 Correct 128 ms 536244 KB Output is correct
21 Correct 127 ms 536400 KB Output is correct
22 Correct 135 ms 537400 KB Output is correct
23 Correct 142 ms 537408 KB Output is correct
24 Correct 135 ms 537508 KB Output is correct
25 Correct 136 ms 537428 KB Output is correct
26 Correct 135 ms 537456 KB Output is correct
27 Correct 153 ms 540880 KB Output is correct
28 Correct 153 ms 541308 KB Output is correct
29 Correct 148 ms 541256 KB Output is correct
30 Correct 169 ms 542160 KB Output is correct
31 Correct 166 ms 542528 KB Output is correct
32 Correct 165 ms 542436 KB Output is correct
33 Correct 792 ms 622848 KB Output is correct
34 Correct 779 ms 626892 KB Output is correct
35 Correct 830 ms 633288 KB Output is correct
36 Correct 1286 ms 636400 KB Output is correct
37 Correct 1287 ms 636884 KB Output is correct
38 Correct 1312 ms 636904 KB Output is correct
39 Correct 582 ms 574656 KB Output is correct
40 Correct 573 ms 574912 KB Output is correct
41 Correct 591 ms 574652 KB Output is correct
42 Correct 532 ms 578200 KB Output is correct
43 Correct 1208 ms 641088 KB Output is correct
44 Correct 1218 ms 641548 KB Output is correct
45 Correct 1227 ms 639984 KB Output is correct
46 Correct 1225 ms 640948 KB Output is correct
47 Correct 1266 ms 641232 KB Output is correct
48 Correct 1259 ms 639680 KB Output is correct
49 Correct 1248 ms 640704 KB Output is correct
50 Correct 1215 ms 641224 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 532720 KB Output is correct
2 Correct 111 ms 532808 KB Output is correct
3 Correct 111 ms 532564 KB Output is correct
4 Correct 110 ms 532560 KB Output is correct
5 Correct 113 ms 532564 KB Output is correct
6 Correct 113 ms 532616 KB Output is correct
7 Correct 112 ms 532560 KB Output is correct
8 Correct 110 ms 532560 KB Output is correct
9 Correct 110 ms 532564 KB Output is correct
10 Correct 110 ms 532692 KB Output is correct
11 Correct 114 ms 532996 KB Output is correct
12 Correct 111 ms 532564 KB Output is correct
13 Correct 111 ms 532564 KB Output is correct
14 Correct 113 ms 532564 KB Output is correct
15 Correct 112 ms 532816 KB Output is correct
16 Correct 114 ms 533452 KB Output is correct
17 Correct 115 ms 533324 KB Output is correct
18 Correct 116 ms 533332 KB Output is correct
19 Correct 132 ms 536576 KB Output is correct
20 Correct 128 ms 536244 KB Output is correct
21 Correct 127 ms 536400 KB Output is correct
22 Correct 135 ms 537400 KB Output is correct
23 Correct 142 ms 537408 KB Output is correct
24 Correct 135 ms 537508 KB Output is correct
25 Correct 136 ms 537428 KB Output is correct
26 Correct 135 ms 537456 KB Output is correct
27 Correct 2420 ms 856248 KB Output is correct
28 Correct 2514 ms 850440 KB Output is correct
29 Correct 2466 ms 849160 KB Output is correct
30 Correct 2449 ms 839972 KB Output is correct
31 Correct 2400 ms 806364 KB Output is correct
32 Execution timed out 3024 ms 883880 KB Time limit exceeded
33 Halted 0 ms 0 KB -