oj.uz

Submission #895443

# Submission time Handle Problem Language Result Execution time Memory
895443 2023-12-30T00:27:22 Z MilosMilutinovic Circle selection (APIO18_circle_selection) C++14
37 / 100
 3000 ms 869544 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 4e6;

int len;
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 i, pair<long long, int> v) {
  for (int x = i + len; x > 0; x >>= 1) {
    vec[x].push_back(v);
  }
}

void Build() {
  for (int x = 1; x < 2 * len; x++) {
    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);
  }
}

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 i, pair<long long, int> v) {
  for (int x = i + len; x > 0; x >>= 1) {
    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);
    }
  }
}

void Add(int x, long long L, long long R) {
  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;
  }
}

void Query(int l, int r, long long L, long long R) {
  for (l += len, r += len + 1; l < r; l >>= 1, r >>= 1) {
    if (l & 1) {
      Add(l++, L, R);
    }
    if (r & 1) {
      Add(--r, 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();
  len = 1;
  while (len < k) {
    len *= 2;
  }
  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(p, make_pair(y[i], i));
  }
  Build();
  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(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(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((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;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 532560 KB Output is correct
2 Correct 110 ms 532560 KB Output is correct
3 Correct 112 ms 532724 KB Output is correct
4 Correct 112 ms 532564 KB Output is correct
5 Correct 109 ms 532632 KB Output is correct
6 Correct 111 ms 532560 KB Output is correct
7 Correct 110 ms 532688 KB Output is correct
8 Correct 111 ms 532788 KB Output is correct
9 Correct 113 ms 532564 KB Output is correct
10 Correct 111 ms 532796 KB Output is correct
11 Correct 110 ms 532560 KB Output is correct
12 Correct 110 ms 532800 KB Output is correct
13 Correct 111 ms 532792 KB Output is correct
14 Correct 109 ms 532564 KB Output is correct
15 Correct 112 ms 532560 KB Output is correct
16 Correct 112 ms 533328 KB Output is correct
17 Correct 114 ms 533628 KB Output is correct
18 Correct 112 ms 533460 KB Output is correct
19 Correct 124 ms 536252 KB Output is correct
20 Correct 124 ms 536400 KB Output is correct
21 Correct 130 ms 536628 KB Output is correct
22 Correct 130 ms 537336 KB Output is correct
23 Correct 132 ms 537312 KB Output is correct
24 Correct 130 ms 537372 KB Output is correct
25 Correct 132 ms 537556 KB Output is correct
26 Correct 130 ms 537288 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2110 ms 852360 KB Output is correct
2 Correct 2118 ms 850360 KB Output is correct
3 Correct 2044 ms 845952 KB Output is correct
4 Correct 2036 ms 856800 KB Output is correct
5 Correct 2171 ms 789504 KB Output is correct
6 Execution timed out 3077 ms 865608 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 532568 KB Output is correct
2 Correct 1132 ms 643204 KB Output is correct
3 Execution timed out 3042 ms 866268 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 3100 ms 869544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 532560 KB Output is correct
2 Correct 110 ms 532560 KB Output is correct
3 Correct 112 ms 532724 KB Output is correct
4 Correct 112 ms 532564 KB Output is correct
5 Correct 109 ms 532632 KB Output is correct
6 Correct 111 ms 532560 KB Output is correct
7 Correct 110 ms 532688 KB Output is correct
8 Correct 111 ms 532788 KB Output is correct
9 Correct 113 ms 532564 KB Output is correct
10 Correct 111 ms 532796 KB Output is correct
11 Correct 110 ms 532560 KB Output is correct
12 Correct 110 ms 532800 KB Output is correct
13 Correct 111 ms 532792 KB Output is correct
14 Correct 109 ms 532564 KB Output is correct
15 Correct 112 ms 532560 KB Output is correct
16 Correct 112 ms 533328 KB Output is correct
17 Correct 114 ms 533628 KB Output is correct
18 Correct 112 ms 533460 KB Output is correct
19 Correct 124 ms 536252 KB Output is correct
20 Correct 124 ms 536400 KB Output is correct
21 Correct 130 ms 536628 KB Output is correct
22 Correct 130 ms 537336 KB Output is correct
23 Correct 132 ms 537312 KB Output is correct
24 Correct 130 ms 537372 KB Output is correct
25 Correct 132 ms 537556 KB Output is correct
26 Correct 130 ms 537288 KB Output is correct
27 Correct 144 ms 541136 KB Output is correct
28 Correct 145 ms 541360 KB Output is correct
29 Correct 145 ms 541644 KB Output is correct
30 Correct 159 ms 542396 KB Output is correct
31 Correct 155 ms 542364 KB Output is correct
32 Correct 155 ms 542416 KB Output is correct
33 Correct 644 ms 624516 KB Output is correct
34 Correct 669 ms 632516 KB Output is correct
35 Correct 696 ms 635440 KB Output is correct
36 Correct 1122 ms 643136 KB Output is correct
37 Correct 1096 ms 642336 KB Output is correct
38 Correct 1142 ms 642548 KB Output is correct
39 Correct 561 ms 574760 KB Output is correct
40 Correct 569 ms 575824 KB Output is correct
41 Correct 577 ms 574164 KB Output is correct
42 Correct 551 ms 582228 KB Output is correct
43 Correct 1018 ms 646536 KB Output is correct
44 Correct 1024 ms 646408 KB Output is correct
45 Correct 1042 ms 645492 KB Output is correct
46 Correct 1031 ms 645028 KB Output is correct
47 Correct 997 ms 645196 KB Output is correct
48 Correct 1006 ms 646648 KB Output is correct
49 Correct 998 ms 645828 KB Output is correct
50 Correct 1016 ms 646340 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 532560 KB Output is correct
2 Correct 110 ms 532560 KB Output is correct
3 Correct 112 ms 532724 KB Output is correct
4 Correct 112 ms 532564 KB Output is correct
5 Correct 109 ms 532632 KB Output is correct
6 Correct 111 ms 532560 KB Output is correct
7 Correct 110 ms 532688 KB Output is correct
8 Correct 111 ms 532788 KB Output is correct
9 Correct 113 ms 532564 KB Output is correct
10 Correct 111 ms 532796 KB Output is correct
11 Correct 110 ms 532560 KB Output is correct
12 Correct 110 ms 532800 KB Output is correct
13 Correct 111 ms 532792 KB Output is correct
14 Correct 109 ms 532564 KB Output is correct
15 Correct 112 ms 532560 KB Output is correct
16 Correct 112 ms 533328 KB Output is correct
17 Correct 114 ms 533628 KB Output is correct
18 Correct 112 ms 533460 KB Output is correct
19 Correct 124 ms 536252 KB Output is correct
20 Correct 124 ms 536400 KB Output is correct
21 Correct 130 ms 536628 KB Output is correct
22 Correct 130 ms 537336 KB Output is correct
23 Correct 132 ms 537312 KB Output is correct
24 Correct 130 ms 537372 KB Output is correct
25 Correct 132 ms 537556 KB Output is correct
26 Correct 130 ms 537288 KB Output is correct
27 Correct 2110 ms 852360 KB Output is correct
28 Correct 2118 ms 850360 KB Output is correct
29 Correct 2044 ms 845952 KB Output is correct
30 Correct 2036 ms 856800 KB Output is correct
31 Correct 2171 ms 789504 KB Output is correct
32 Execution timed out 3077 ms 865608 KB Time limit exceeded
33 Halted 0 ms 0 KB -