oj.uz

Submission #895449

# Submission time Handle Problem Language Result Execution time Memory
895449 2023-12-30T00:47:26 Z MilosMilutinovic Circle selection (APIO18_circle_selection) C++14
37 / 100
 3000 ms 860852 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 (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][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 low = 0, high = (int) vec[x].size() - 1, idx = high + 1;
  while (low <= high) {
    int mid = low + high >> 1;
    if (vec[x][mid].first >= L) {
      idx = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  //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;
}

Compilation message

circle_selection.cpp: In function 'void Add(int, long long int, long long int)':
circle_selection.cpp:76:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |     int mid = low + high >> 1;
      |               ~~~~^~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 538196 KB Output is correct
2 Correct 111 ms 538236 KB Output is correct
3 Correct 112 ms 538184 KB Output is correct
4 Correct 111 ms 538228 KB Output is correct
5 Correct 113 ms 538036 KB Output is correct
6 Correct 111 ms 538192 KB Output is correct
7 Correct 111 ms 538120 KB Output is correct
8 Correct 116 ms 538192 KB Output is correct
9 Correct 110 ms 538292 KB Output is correct
10 Correct 114 ms 538196 KB Output is correct
11 Correct 117 ms 538452 KB Output is correct
12 Correct 112 ms 538164 KB Output is correct
13 Correct 112 ms 538196 KB Output is correct
14 Correct 112 ms 538096 KB Output is correct
15 Correct 113 ms 538448 KB Output is correct
16 Correct 114 ms 538708 KB Output is correct
17 Correct 113 ms 538808 KB Output is correct
18 Correct 115 ms 538704 KB Output is correct
19 Correct 129 ms 541712 KB Output is correct
20 Correct 124 ms 541552 KB Output is correct
21 Correct 126 ms 541672 KB Output is correct
22 Correct 142 ms 542580 KB Output is correct
23 Correct 133 ms 542464 KB Output is correct
24 Correct 130 ms 542544 KB Output is correct
25 Correct 143 ms 542656 KB Output is correct
26 Correct 134 ms 542652 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2182 ms 842688 KB Output is correct
2 Correct 2191 ms 839852 KB Output is correct
3 Correct 2146 ms 837376 KB Output is correct
4 Correct 2191 ms 846552 KB Output is correct
5 Correct 2305 ms 783236 KB Output is correct
6 Execution timed out 3088 ms 859716 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 538240 KB Output is correct
2 Correct 1235 ms 643756 KB Output is correct
3 Execution timed out 3083 ms 859272 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 3039 ms 860852 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 538196 KB Output is correct
2 Correct 111 ms 538236 KB Output is correct
3 Correct 112 ms 538184 KB Output is correct
4 Correct 111 ms 538228 KB Output is correct
5 Correct 113 ms 538036 KB Output is correct
6 Correct 111 ms 538192 KB Output is correct
7 Correct 111 ms 538120 KB Output is correct
8 Correct 116 ms 538192 KB Output is correct
9 Correct 110 ms 538292 KB Output is correct
10 Correct 114 ms 538196 KB Output is correct
11 Correct 117 ms 538452 KB Output is correct
12 Correct 112 ms 538164 KB Output is correct
13 Correct 112 ms 538196 KB Output is correct
14 Correct 112 ms 538096 KB Output is correct
15 Correct 113 ms 538448 KB Output is correct
16 Correct 114 ms 538708 KB Output is correct
17 Correct 113 ms 538808 KB Output is correct
18 Correct 115 ms 538704 KB Output is correct
19 Correct 129 ms 541712 KB Output is correct
20 Correct 124 ms 541552 KB Output is correct
21 Correct 126 ms 541672 KB Output is correct
22 Correct 142 ms 542580 KB Output is correct
23 Correct 133 ms 542464 KB Output is correct
24 Correct 130 ms 542544 KB Output is correct
25 Correct 143 ms 542656 KB Output is correct
26 Correct 134 ms 542652 KB Output is correct
27 Correct 144 ms 545740 KB Output is correct
28 Correct 146 ms 546036 KB Output is correct
29 Correct 148 ms 546216 KB Output is correct
30 Correct 158 ms 547280 KB Output is correct
31 Correct 161 ms 547220 KB Output is correct
32 Correct 161 ms 547208 KB Output is correct
33 Correct 682 ms 626072 KB Output is correct
34 Correct 704 ms 632716 KB Output is correct
35 Correct 728 ms 635616 KB Output is correct
36 Correct 1251 ms 644324 KB Output is correct
37 Correct 1170 ms 644492 KB Output is correct
38 Correct 1221 ms 644040 KB Output is correct
39 Correct 622 ms 576664 KB Output is correct
40 Correct 594 ms 576808 KB Output is correct
41 Correct 601 ms 576316 KB Output is correct
42 Correct 581 ms 585188 KB Output is correct
43 Correct 1129 ms 647728 KB Output is correct
44 Correct 1146 ms 647728 KB Output is correct
45 Correct 1084 ms 647544 KB Output is correct
46 Correct 1081 ms 647496 KB Output is correct
47 Correct 1150 ms 647480 KB Output is correct
48 Correct 1077 ms 647840 KB Output is correct
49 Correct 1165 ms 647520 KB Output is correct
50 Correct 1119 ms 648860 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 538196 KB Output is correct
2 Correct 111 ms 538236 KB Output is correct
3 Correct 112 ms 538184 KB Output is correct
4 Correct 111 ms 538228 KB Output is correct
5 Correct 113 ms 538036 KB Output is correct
6 Correct 111 ms 538192 KB Output is correct
7 Correct 111 ms 538120 KB Output is correct
8 Correct 116 ms 538192 KB Output is correct
9 Correct 110 ms 538292 KB Output is correct
10 Correct 114 ms 538196 KB Output is correct
11 Correct 117 ms 538452 KB Output is correct
12 Correct 112 ms 538164 KB Output is correct
13 Correct 112 ms 538196 KB Output is correct
14 Correct 112 ms 538096 KB Output is correct
15 Correct 113 ms 538448 KB Output is correct
16 Correct 114 ms 538708 KB Output is correct
17 Correct 113 ms 538808 KB Output is correct
18 Correct 115 ms 538704 KB Output is correct
19 Correct 129 ms 541712 KB Output is correct
20 Correct 124 ms 541552 KB Output is correct
21 Correct 126 ms 541672 KB Output is correct
22 Correct 142 ms 542580 KB Output is correct
23 Correct 133 ms 542464 KB Output is correct
24 Correct 130 ms 542544 KB Output is correct
25 Correct 143 ms 542656 KB Output is correct
26 Correct 134 ms 542652 KB Output is correct
27 Correct 2182 ms 842688 KB Output is correct
28 Correct 2191 ms 839852 KB Output is correct
29 Correct 2146 ms 837376 KB Output is correct
30 Correct 2191 ms 846552 KB Output is correct
31 Correct 2305 ms 783236 KB Output is correct
32 Execution timed out 3088 ms 859716 KB Time limit exceeded
33 Halted 0 ms 0 KB -