제출 #260991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
260991		emanIaicepsa	원 고르기 (APIO18_circle_selection)	C++14	12 / 100	831 ms	55288 KiB

circle_selection

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define vi vector<int>
#define pb emplace_back
#define fi first
#define se second
#define all(n) (n).begin(),(n).end()
#define mem(n,m) memset(n,m,sizeof(n))
#define IOS ios::sync_with_stdio(0), cin.tie(0)
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
template<typename A> void _do(A x){cerr<<x<<'\n';}
template<typename A,typename ...B> void _do(A x,B ...y){cerr<<x<<", ";_do(y...);}

struct circle{
    ll x, y, r, id;
    bool operator<(const circle &b){
        if(r!=b.r) return r>b.r;
        return id<b.id;
    }
}arr[300005];

int n, del[300005], fr[300005], ba[300005];

bool in(ll i,ll j){
    ll R = arr[i].r + arr[j].r;
    ll dx = arr[i].x - arr[j].x, dy = arr[i].y - arr[j].y;
    return dx*dx + dy*dy <= R*R;
}

set<pii> s;

signed main(){
	IOS;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i].x>>arr[i].y>>arr[i].r;
        arr[i].id = i;
        s.insert({arr[i].x - arr[i].r, i});
        s.insert({arr[i].x + arr[i].r, i});
    }

    sort(arr+1,arr+1+n);

    for(int i=1;i<=n;i++){
        if(del[arr[i].id]) continue;
        //dbg(arr[i].id);
        auto iter = s.lower_bound({arr[i].x-arr[i].r,-1});
        while(iter!=s.end() && iter->fi <= arr[i].x + arr[i].r ){
            //dbg(iter->fi, iter->se);
            if(!del[iter->se]) del[iter->se] = arr[i].id;
            iter = s.erase(iter);
        }
        del[arr[i].id] = arr[i].id;
    }

    for(int i=1;i<=n;i++) cout<<del[i]<<" \n"[i==n];

}
/*
11
9 0 2
13 0 1
11 0 2
3 0 2
3 0 1
12 0 1
9 0 5
2 0 2
5 0 1
14 0 2
14 0 1
*/

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