Submission #932235

#	Time	Username	Problem	Language	Result	Execution time	Memory
932235		beepbeepsheep	Circle selection (APIO18_circle_selection)	C++17	0 / 100	1380 ms	1048576 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define iii tuple<ll,ll,ll>
#define iiii tuple<ll,ll,ll,ll>

const ll maxn=3e5+5;
const ll mod=1e9+7;
const ll inf=1e15;

iii arr[maxn];
ll ans[maxn];
iiii ord[maxn];
struct node{
    ll s,e,m,val,flag;
    node *l,*r;
    node(ll _s, ll _e){
        s=_s,e=_e,m=(s+e)>>1,val=0,flag=inf;
        l=nullptr,r=nullptr;
    }
    void create(){
        if (l) return;
        if (s==e) return;
        l=new node(s,m),r=new node(m+1,e);
    }
    void prop(){
        if (!flag) return;
        val+=flag;
        if (s==e){
            flag=0;
            return;
        }
        create();
        l->flag=flag;
        r->flag=flag;
        val=flag;
        flag=0;
    }
    void upd(ll x, ll y, ll v){
        if (x<=s && e<=y){
            flag=v;
            return;
        }
        create();
        if (x>m) r->upd(x,y,v);
        else if (y<=m) l->upd(x,y,v);
        else l->upd(x,y,v),r->upd(x,y,v);
        l->prop(),r->prop();
        val=min(l->val,r->val);
    }
    ll query(ll x, ll y){
        prop();
        if (x<=s && e<=y) return val;
        create();
        if (x>m) return r->query(x,y);
        if (y<=m) return l->query(x,y);
        return min(l->query(x,y),r->query(x,y));
    }
}*root;

bool cmp(iiii a, iiii b){
    if (get<2>(a)==get<2>(b)) return get<3>(a)< get<3>(b);
    return get<2>(a)>get<2>(b);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,a,b,c;
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a>>b>>c;
        assert(b==0);
        arr[i]={a,b,c};
        ord[i]={a,b,c,i};
    }
    sort(ord+1,ord+n+1,cmp);
    ll x,y,r,idx;
    root=new node(-mod,mod);

    for (int i=1;i<=n;i++){
        tie(x,y,r,idx)=ord[i];
        ll res=root->query(x-r,x+r);
        //cerr<<res<<endl;
        if (res==inf){
            ans[idx]=idx;
            root->upd(x-r,x+r,i);
        } else{
            ans[idx]=get<3>(ord[res]);
        }
    }
    for (int i=1;i<=n;i++) cout<<ans[i]<<' ';
    return 0;
}

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