oj.uz

Submission #895446

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

using namespace std;

const int MAX = 3e5;
const int N = 4e6;

long long x[MAX], y[MAX], r[MAX];
int res[MAX], x_pos[N], len, cur;
vector<pair<long long, int>> vec[N];
vector<int> xs;
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 Check(int idx) {
  if ((x[cur] - x[idx]) * 1LL * (x[cur] - x[idx]) + (y[cur] - y[idx]) * 1LL * (y[cur] - y[idx]) <= (r[cur] + r[idx]) * 1LL * (r[cur] + r[idx])) {
    res[idx] = cur;
    Delete(x_pos[idx], make_pair(y[idx], idx));
  }
}

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;
    }
    Check(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;
  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;
    }
  });
  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();
  for (int i = 0; i < n; i++) {
    x_pos[i] = (int) (lower_bound(xs.begin(), xs.end(), x[i]) - xs.begin());
  }
  len = 1;
  while (len < k) {
    len *= 2;
  }
  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;
    }
    cur = i;
    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 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 135 ms 542284 KB Output is correct
2 Correct 120 ms 542248 KB Output is correct
3 Correct 115 ms 542336 KB Output is correct
4 Correct 117 ms 542168 KB Output is correct
5 Correct 119 ms 542336 KB Output is correct
6 Correct 114 ms 542260 KB Output is correct
7 Correct 112 ms 542288 KB Output is correct
8 Correct 114 ms 542292 KB Output is correct
9 Correct 121 ms 542328 KB Output is correct
10 Correct 112 ms 542288 KB Output is correct
11 Correct 115 ms 542348 KB Output is correct
12 Correct 115 ms 542268 KB Output is correct
13 Correct 112 ms 542284 KB Output is correct
14 Correct 113 ms 542416 KB Output is correct
15 Correct 112 ms 542292 KB Output is correct
16 Correct 125 ms 542876 KB Output is correct
17 Correct 115 ms 543056 KB Output is correct
18 Correct 115 ms 543032 KB Output is correct
19 Correct 129 ms 545616 KB Output is correct
20 Correct 128 ms 545700 KB Output is correct
21 Correct 126 ms 545872 KB Output is correct
22 Correct 133 ms 546600 KB Output is correct
23 Correct 139 ms 546888 KB Output is correct
24 Correct 130 ms 546808 KB Output is correct
25 Correct 131 ms 546804 KB Output is correct
26 Correct 132 ms 546724 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2159 ms 843756 KB Output is correct
2 Correct 2144 ms 845104 KB Output is correct
3 Correct 2142 ms 840432 KB Output is correct
4 Correct 2147 ms 847804 KB Output is correct
5 Correct 2301 ms 786232 KB Output is correct
6 Execution timed out 3082 ms 864520 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 542108 KB Output is correct
2 Correct 1173 ms 646344 KB Output is correct
3 Execution timed out 3070 ms 861404 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 3052 ms 863236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 542284 KB Output is correct
2 Correct 120 ms 542248 KB Output is correct
3 Correct 115 ms 542336 KB Output is correct
4 Correct 117 ms 542168 KB Output is correct
5 Correct 119 ms 542336 KB Output is correct
6 Correct 114 ms 542260 KB Output is correct
7 Correct 112 ms 542288 KB Output is correct
8 Correct 114 ms 542292 KB Output is correct
9 Correct 121 ms 542328 KB Output is correct
10 Correct 112 ms 542288 KB Output is correct
11 Correct 115 ms 542348 KB Output is correct
12 Correct 115 ms 542268 KB Output is correct
13 Correct 112 ms 542284 KB Output is correct
14 Correct 113 ms 542416 KB Output is correct
15 Correct 112 ms 542292 KB Output is correct
16 Correct 125 ms 542876 KB Output is correct
17 Correct 115 ms 543056 KB Output is correct
18 Correct 115 ms 543032 KB Output is correct
19 Correct 129 ms 545616 KB Output is correct
20 Correct 128 ms 545700 KB Output is correct
21 Correct 126 ms 545872 KB Output is correct
22 Correct 133 ms 546600 KB Output is correct
23 Correct 139 ms 546888 KB Output is correct
24 Correct 130 ms 546808 KB Output is correct
25 Correct 131 ms 546804 KB Output is correct
26 Correct 132 ms 546724 KB Output is correct
27 Correct 144 ms 549908 KB Output is correct
28 Correct 147 ms 550144 KB Output is correct
29 Correct 147 ms 550228 KB Output is correct
30 Correct 161 ms 551372 KB Output is correct
31 Correct 162 ms 551372 KB Output is correct
32 Correct 160 ms 551496 KB Output is correct
33 Correct 676 ms 628520 KB Output is correct
34 Correct 663 ms 635136 KB Output is correct
35 Correct 701 ms 637900 KB Output is correct
36 Correct 1134 ms 646860 KB Output is correct
37 Correct 1141 ms 646864 KB Output is correct
38 Correct 1196 ms 646492 KB Output is correct
39 Correct 557 ms 579060 KB Output is correct
40 Correct 619 ms 579252 KB Output is correct
41 Correct 606 ms 578768 KB Output is correct
42 Correct 539 ms 587524 KB Output is correct
43 Correct 1134 ms 650188 KB Output is correct
44 Correct 1095 ms 649948 KB Output is correct
45 Correct 1072 ms 650032 KB Output is correct
46 Correct 1062 ms 651296 KB Output is correct
47 Correct 1105 ms 649928 KB Output is correct
48 Correct 1039 ms 649912 KB Output is correct
49 Correct 1071 ms 650192 KB Output is correct
50 Correct 1125 ms 650064 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 542284 KB Output is correct
2 Correct 120 ms 542248 KB Output is correct
3 Correct 115 ms 542336 KB Output is correct
4 Correct 117 ms 542168 KB Output is correct
5 Correct 119 ms 542336 KB Output is correct
6 Correct 114 ms 542260 KB Output is correct
7 Correct 112 ms 542288 KB Output is correct
8 Correct 114 ms 542292 KB Output is correct
9 Correct 121 ms 542328 KB Output is correct
10 Correct 112 ms 542288 KB Output is correct
11 Correct 115 ms 542348 KB Output is correct
12 Correct 115 ms 542268 KB Output is correct
13 Correct 112 ms 542284 KB Output is correct
14 Correct 113 ms 542416 KB Output is correct
15 Correct 112 ms 542292 KB Output is correct
16 Correct 125 ms 542876 KB Output is correct
17 Correct 115 ms 543056 KB Output is correct
18 Correct 115 ms 543032 KB Output is correct
19 Correct 129 ms 545616 KB Output is correct
20 Correct 128 ms 545700 KB Output is correct
21 Correct 126 ms 545872 KB Output is correct
22 Correct 133 ms 546600 KB Output is correct
23 Correct 139 ms 546888 KB Output is correct
24 Correct 130 ms 546808 KB Output is correct
25 Correct 131 ms 546804 KB Output is correct
26 Correct 132 ms 546724 KB Output is correct
27 Correct 2159 ms 843756 KB Output is correct
28 Correct 2144 ms 845104 KB Output is correct
29 Correct 2142 ms 840432 KB Output is correct
30 Correct 2147 ms 847804 KB Output is correct
31 Correct 2301 ms 786232 KB Output is correct
32 Execution timed out 3082 ms 864520 KB Time limit exceeded
33 Halted 0 ms 0 KB -