Submission #397550

#	Time	Username	Problem	Language	Result	Execution time	Memory
397550		parsabahrami	Circle selection (APIO18_circle_selection)	C++17	100 / 100	2423 ms	403440 KiB

circle_selection

/* There's someone in my head but it's not me */ 
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("avx")

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;

#define all(x) x.begin(), x.end()
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second
#define lc                          i << 1
#define rc                          lc | 1

const int N = 3e5 + 4, MOD = 1e9 + 7;
int n, X[N], Y[N], R[N], ord[N], ret[N], id[N]; ll base[N];
set<pii> seg[N << 1]; vector <ll> cm;
vector<pii> vec[N << 1];

bool cmp(int i, int j) {
	if (R[i] == R[j]) return i < j;
    return R[i] > R[j];
}

int intersect(int i, int j) {
    return (base[i] + base[j] + 2ll * (1ll * X[i] * X[j] + 1ll * Y[i] * Y[j] + 1ll * R[i] * R[j])) >= 0;
}

int lwr(ll x) {
    return lower_bound(all(cm), x) - cm.begin();
}

void add(int pos, pii x) {
    pos += n;
    vec[pos].push_back(x);
}

void get(int ql, int qr, ll yl, ll yr, int p) {
    ql += n, qr += n + 1;
    while (qr - ql > 0) {
        if (ql & 1) {
            for (auto it = seg[ql].lower_bound({yl, -1e9}); it != seg[ql].end() && it->F <= yr; ) {
                if (ret[it->S]) it = seg[ql].erase(it);
                else if (intersect(p, it->S)) ret[it->S] = p, it = seg[ql].erase(it);
                else it++;
            }
            ql++;
        } 
        if (qr & 1) {
            qr--;
            for (auto it = seg[qr].lower_bound({yl, -1e9}); it != seg[qr].end() && it->F <= yr; ) {
                if (ret[it->S]) it = seg[qr].erase(it);
                else if (intersect(p, it->S)) ret[it->S] = p, it = seg[qr].erase(it);
                else it++;
            }
        }
        qr >>= 1, ql >>= 1;
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) 
        scanf("%d%d%d", &X[i], &Y[i], &R[i]), base[i] = 1ll * R[i] * R[i] - 1ll * X[i] * X[i] - 1ll * Y[i] * Y[i], cm.push_back(X[i]), ord[i] = i;
    sort(ord + 1, ord + n + 1, cmp);
    sort(all(cm));
    cm.resize(unique(all(cm)) - cm.begin());
    for(int i = 1; i <= n; i ++) {
	    int I = ord[i];
	    add(lwr(X[I]) + 1, make_pair(Y[I], I));
    }
    for (int i = n + 1; i <= 2 * n + 2; i++) {
	    sort(all(vec[i]));
    }
    for(int i = n; i >= 1; i--) {
	    merge(all(vec[lc]), all(vec[rc]), back_inserter(vec[i]));
    }
    for (int i = 0; i <= 2 * n + 2; i++) {
	    seg[i] = set<pii>(vec[i].begin(), vec[i].end());
    }
    for (int _ = 1; _ <= n; _++) {
        int i = ord[_];
        if (ret[i]) continue;
        get(lwr(X[i] - 2ll * R[i]) + 1, lwr(X[i] + 2ll * R[i] + 1), Y[i] - 2ll * R[i], Y[i] + 2ll * R[i], i);
    }
    for (int i = 1; i <= n; i++) printf("%d ", ret[i]);
    printf("\n");
    return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
circle_selection.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |         scanf("%d%d%d", &X[i], &Y[i], &R[i]), base[i] = 1ll * R[i] * R[i] - 1ll * X[i] * X[i] - 1ll * Y[i] * Y[i], cm.push_back(X[i]), ord[i] = i;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13