# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
966664 | Soumya1 | Circle selection (APIO18_circle_selection) | C++17 | 3017 ms | 200216 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int mxN = 3e5 + 5;
int x[mxN], y[mxN], r[mxN], pos[mxN], ans[mxN];
set<pair<int, int>> st[2 * 4 * mxN];
void update(int x, int lx, int rx, int l, int r, int i) {
if (l > rx || lx > r) return;
if (l <= lx && r >= rx) {
st[x].insert({y[i], i});
return;
}
int mx = (lx + rx) >> 1;
update(x << 1, lx, mx, l, r, i);
update(x << 1 | 1, mx + 1, rx, l, r, i);
}
bool intersect(int a, int b) {
return 1LL * (x[a] - x[b]) * (x[a] - x[b]) + 1LL * (y[a] - y[b]) * (y[a] - y[b]) <= 1LL * (r[a] + r[b]) * (r[a] + r[b]);
}
void update(int a, int b) {
if (!intersect(a, b)) return;
if (pos[b] < pos[ans[a]]) ans[a] = b;
}
void check(int x, int i) {
auto it = lower_bound(st[x].begin(), st[x].end(), pair<int, int> {y[i], -2e9});
if (it != st[x].end()) {
update(i, (*it).second);
it++;
if (it != st[x].end()) {
update(i, (*it).second);
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |