제출 #742326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
742326		victor_gao	원 고르기 (APIO18_circle_selection)	C++17	12 / 100	1190 ms	61028 KiB

circle_selection

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 300015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,ans[N],X[N],Y[N],R[N];
set<pii>sl,sr;
vector<pair<pii,int> >all;
bool cmp(pair<pii,int>a,pair<pii,int>b){
    if (a.x.x!=b.x.x) return a.x.x>b.x.x;
    else return a.x.y<b.x.y;
}
signed main(){
  //  fast
    cin>>n;
    for (int i=1;i<=n;i++){
        int a,b,c; cin>>a>>b>>c;
        X[i]=a; Y[i]=b; R[i]=c;
        sl.insert(pii(a-c,i));
        sr.insert(pii(a+c,i));
        all.push_back({{c,i},a});
    }
    sort(all.begin(),all.end(),cmp);
    for (auto [tmp,p]:all){
        auto [r,i]=tmp;
        if (ans[i]) continue;
        ans[i]=i;
        sl.erase(pii(p-r,i));
        sr.erase(pii(p+r,i));
        if (!sl.empty()){
            auto it=sl.lower_bound(pii(p-r,0LL));
            while (it!=sl.end()&&(it->x)<=p+r){
                int now=(it->y); it=sl.erase(it);
                ans[now]=i;
                sr.erase(pii(X[now]+R[now],now));
            }
        }
        if (!sr.empty()){
            auto it=sr.lower_bound(pii(p-r,0LL));
            while (it!=sr.end()&&(it->x)<=p+r){
                int now=(it->y); it=sr.erase(it);
                ans[now]=i;
                sl.erase(pii(X[now]-R[now],now));
            }
        }
    }
    for (int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    cout<<'\n';
}
/*
5
2 0 5
1 0 1
19 0 10
3 0 2
5 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