oj.uz

Submission #932237

# Submission time Handle Problem Language Result Execution time Memory
932237 2024-02-23T06:07:17 Z beepbeepsheep Circle selection (APIO18_circle_selection) C++17
12 / 100
 1240 ms 848692 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll int
#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;
}

Compilation message

circle_selection.cpp:11:14: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+15' to '2147483647' [-Woverflow]
   11 | const ll inf=1e15;
      |              ^~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1240 ms 848692 KB Output is correct
2 Correct 1231 ms 840732 KB Output is correct
3 Correct 1231 ms 785184 KB Output is correct
4 Correct 1151 ms 797168 KB Output is correct
5 Correct 350 ms 48628 KB Output is correct
6 Correct 768 ms 362688 KB Output is correct
7 Correct 612 ms 156992 KB Output is correct
8 Correct 629 ms 207868 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -