oj.uz

Submission #895451

# Submission time Handle Problem Language Result Execution time Memory
895451 2023-12-30T00:52:15 Z MilosMilutinovic Circle selection (APIO18_circle_selection) C++14
37 / 100
 3000 ms 862684 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], 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 (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][a]);
}

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((int) (lower_bound(xs.begin(), xs.end(), x[idx]) - xs.begin()), 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();
  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 110 ms 538188 KB Output is correct
2 Correct 114 ms 538228 KB Output is correct
3 Correct 110 ms 538104 KB Output is correct
4 Correct 115 ms 538196 KB Output is correct
5 Correct 111 ms 538236 KB Output is correct
6 Correct 112 ms 538164 KB Output is correct
7 Correct 111 ms 538044 KB Output is correct
8 Correct 111 ms 538248 KB Output is correct
9 Correct 113 ms 538264 KB Output is correct
10 Correct 111 ms 538288 KB Output is correct
11 Correct 111 ms 538192 KB Output is correct
12 Correct 117 ms 538192 KB Output is correct
13 Correct 111 ms 538308 KB Output is correct
14 Correct 111 ms 538096 KB Output is correct
15 Correct 115 ms 538196 KB Output is correct
16 Correct 118 ms 539080 KB Output is correct
17 Correct 114 ms 538804 KB Output is correct
18 Correct 114 ms 538708 KB Output is correct
19 Correct 125 ms 541588 KB Output is correct
20 Correct 125 ms 541652 KB Output is correct
21 Correct 125 ms 541536 KB Output is correct
22 Correct 132 ms 542692 KB Output is correct
23 Correct 132 ms 542532 KB Output is correct
24 Correct 139 ms 542800 KB Output is correct
25 Correct 131 ms 542800 KB Output is correct
26 Correct 131 ms 542548 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2150 ms 844564 KB Output is correct
2 Correct 2176 ms 841668 KB Output is correct
3 Correct 2139 ms 835520 KB Output is correct
4 Correct 2164 ms 845552 KB Output is correct
5 Correct 2294 ms 782276 KB Output is correct
6 Execution timed out 3037 ms 862684 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 538224 KB Output is correct
2 Correct 1250 ms 643804 KB Output is correct
3 Execution timed out 3044 ms 859460 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 3058 ms 858576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 538188 KB Output is correct
2 Correct 114 ms 538228 KB Output is correct
3 Correct 110 ms 538104 KB Output is correct
4 Correct 115 ms 538196 KB Output is correct
5 Correct 111 ms 538236 KB Output is correct
6 Correct 112 ms 538164 KB Output is correct
7 Correct 111 ms 538044 KB Output is correct
8 Correct 111 ms 538248 KB Output is correct
9 Correct 113 ms 538264 KB Output is correct
10 Correct 111 ms 538288 KB Output is correct
11 Correct 111 ms 538192 KB Output is correct
12 Correct 117 ms 538192 KB Output is correct
13 Correct 111 ms 538308 KB Output is correct
14 Correct 111 ms 538096 KB Output is correct
15 Correct 115 ms 538196 KB Output is correct
16 Correct 118 ms 539080 KB Output is correct
17 Correct 114 ms 538804 KB Output is correct
18 Correct 114 ms 538708 KB Output is correct
19 Correct 125 ms 541588 KB Output is correct
20 Correct 125 ms 541652 KB Output is correct
21 Correct 125 ms 541536 KB Output is correct
22 Correct 132 ms 542692 KB Output is correct
23 Correct 132 ms 542532 KB Output is correct
24 Correct 139 ms 542800 KB Output is correct
25 Correct 131 ms 542800 KB Output is correct
26 Correct 131 ms 542548 KB Output is correct
27 Correct 146 ms 545880 KB Output is correct
28 Correct 146 ms 546100 KB Output is correct
29 Correct 144 ms 546000 KB Output is correct
30 Correct 160 ms 547100 KB Output is correct
31 Correct 163 ms 547228 KB Output is correct
32 Correct 162 ms 547400 KB Output is correct
33 Correct 713 ms 626312 KB Output is correct
34 Correct 688 ms 632780 KB Output is correct
35 Correct 728 ms 635488 KB Output is correct
36 Correct 1195 ms 644320 KB Output is correct
37 Correct 1193 ms 644668 KB Output is correct
38 Correct 1208 ms 643952 KB Output is correct
39 Correct 593 ms 576460 KB Output is correct
40 Correct 596 ms 576960 KB Output is correct
41 Correct 599 ms 576368 KB Output is correct
42 Correct 559 ms 585312 KB Output is correct
43 Correct 1102 ms 647676 KB Output is correct
44 Correct 1087 ms 647624 KB Output is correct
45 Correct 1119 ms 647624 KB Output is correct
46 Correct 1085 ms 647604 KB Output is correct
47 Correct 1088 ms 647644 KB Output is correct
48 Correct 1105 ms 647456 KB Output is correct
49 Correct 1092 ms 647348 KB Output is correct
50 Correct 1150 ms 647472 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 538188 KB Output is correct
2 Correct 114 ms 538228 KB Output is correct
3 Correct 110 ms 538104 KB Output is correct
4 Correct 115 ms 538196 KB Output is correct
5 Correct 111 ms 538236 KB Output is correct
6 Correct 112 ms 538164 KB Output is correct
7 Correct 111 ms 538044 KB Output is correct
8 Correct 111 ms 538248 KB Output is correct
9 Correct 113 ms 538264 KB Output is correct
10 Correct 111 ms 538288 KB Output is correct
11 Correct 111 ms 538192 KB Output is correct
12 Correct 117 ms 538192 KB Output is correct
13 Correct 111 ms 538308 KB Output is correct
14 Correct 111 ms 538096 KB Output is correct
15 Correct 115 ms 538196 KB Output is correct
16 Correct 118 ms 539080 KB Output is correct
17 Correct 114 ms 538804 KB Output is correct
18 Correct 114 ms 538708 KB Output is correct
19 Correct 125 ms 541588 KB Output is correct
20 Correct 125 ms 541652 KB Output is correct
21 Correct 125 ms 541536 KB Output is correct
22 Correct 132 ms 542692 KB Output is correct
23 Correct 132 ms 542532 KB Output is correct
24 Correct 139 ms 542800 KB Output is correct
25 Correct 131 ms 542800 KB Output is correct
26 Correct 131 ms 542548 KB Output is correct
27 Correct 2150 ms 844564 KB Output is correct
28 Correct 2176 ms 841668 KB Output is correct
29 Correct 2139 ms 835520 KB Output is correct
30 Correct 2164 ms 845552 KB Output is correct
31 Correct 2294 ms 782276 KB Output is correct
32 Execution timed out 3037 ms 862684 KB Time limit exceeded
33 Halted 0 ms 0 KB -