Submission #966664

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
9666642024-04-20 07:54:02Soumya1Circle selection (APIO18_circle_selection)C++17
72 / 100
3017 ms200216 KiB
#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);
}
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...