Submission #49662

#	Time	Username	Problem	Language	Result	Execution time	Memory
49662		gs14004	원 고르기 (APIO18_circle_selection)	C++17	100 / 100	2027 ms	464704 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
 
#define MAXN 300005
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
typedef long long lld;
typedef pair<int, int> pii;
 
int N;
int X[MAXN], Y[MAXN], R[MAXN], A[MAXN], P[MAXN], Q[MAXN];
int ans[MAXN];
 
int XX[MAXN*2], XC;
 
const int TS = 2097152, ST = TS/2-1;
struct NODE {
    vector <pii> arr;
    vector <int> nxt;
    int find(int n){ return nxt[n] == n ? n : (nxt[n] = find(nxt[n])); }
    void relax(){
        int n = sz(arr);
        nxt.resize(n+1);
        for (int i=0;i<=n;i++) nxt[i] = i;
    }
    void merge(const NODE &a, const NODE &b){
        int n = sz(a.arr), m = sz(b.arr);
        arr.resize(n+m);
        for (int i=0,j=0,k=0;i<n||j<m;){
            if (j == m || i < n && a.arr[i] < b.arr[j]) arr[k++] = a.arr[i++];
            else arr[k++] = b.arr[j++];
        }
        relax();
    }
} tree[TS];
 
inline bool intersect(int a, int b){ return (lld)(X[a]-X[b])*(X[a]-X[b]) + (lld)(Y[a]-Y[b])*(Y[a]-Y[b]) <= (lld)(R[a]+R[b])*(R[a]+R[b]); }
 
void doIt(int n)
{
    auto iterate = [&](NODE &v){
        for (int i=lower_bound(all(v.arr), pii(Y[n]-R[n], 0))-v.arr.begin();;i++){
            i = v.find(i);
            if (i >= sz(v.arr) || v.arr[i].first > Y[n]+R[n]) break;
            int t = v.arr[i].second;
            if (ans[t])
                v.nxt[i] = v.find(i+1);
            else if (intersect(n, t))
                ans[t] = n;
        }
    };
    for (int l=ST+P[n],r=ST+Q[n];l<=r;l>>=1,r>>=1){
        if (l&1) iterate(tree[l++]);
        if (!(r&1)) iterate(tree[r--]);
    }
}
 
int main()
{
    scanf("%d", &N);
    for (int i=1;i<=N;i++){
        scanf("%d%d%d", X+i, Y+i, R+i);
        A[i] = i;
        XX[++XC] = X[i]-R[i];
        XX[++XC] = X[i]+R[i];
    }
    sort(XX+1, XX+XC+1); XC = unique(XX+1, XX+XC+1)-XX-1;
    sort(A+1, A+N+1, [](const int &a, const int &b){
        return R[a] != R[b] ? R[a] > R[b] : a < b;
    });
 
    for (int i=1;i<=N;i++){
        P[i] = lower_bound(XX+1, XX+XC+1, X[i]-R[i]) - XX;
        Q[i] = lower_bound(XX+1, XX+XC+1, X[i]+R[i]) - XX;
        tree[ST+P[i]].arr.pb({Y[i]-R[i], i});
        tree[ST+P[i]].arr.pb({Y[i]+R[i], i});
        tree[ST+Q[i]].arr.pb({Y[i]-R[i], i});
        tree[ST+Q[i]].arr.pb({Y[i]+R[i], i});
    }
    for (int i=1;i<=XC;i++) sort(all(tree[ST+i].arr)), tree[ST+i].relax();
    for (int i=ST;i;i--) tree[i].merge(tree[i+i], tree[i+i+1]);
 
    for (int i=1;i<=N;i++) if (!ans[A[i]])
        doIt(A[i]);
         
    for (int i=1;i<=N;i++) printf("%d%s", ans[i], i < N ? " " : "");
    puts("");
}

Compilation message (stderr)

circle_selection.cpp: In member function 'void NODE::merge(const NODE&, const NODE&)':
circle_selection.cpp:31:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             if (j == m || i < n && a.arr[i] < b.arr[j]) arr[k++] = a.arr[i++];
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
circle_selection.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", X+i, Y+i, R+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