Submission #394003

#	Time	Username	Problem	Language	Result	Execution time	Memory
394003		79brue	Circle selection (APIO18_circle_selection)	C++14	12 / 100	1457 ms	73588 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Circle{
    ll x, y, r; int idx;
    Circle(ll x, ll y, ll r, int idx): x(x), y(y), r(r), idx(idx){}
    bool touch(const Circle &nxt)const{
        return (x-nxt.x) * (x-nxt.x) + (y-nxt.y) * (y-nxt.y) <= (r+nxt.r) * (r+nxt.r);
    }
    bool operator<(const Circle &nxt)const{
        if(r!=nxt.r) return r>nxt.r;
        return idx<nxt.idx;
    }
};
vector<Circle> vec;
int indexes[300002];

int tree[2400002], lazy[2400002];
void init(int i, int l, int r){
    tree[i] = lazy[i] = 1e9;
    if(l==r) return;
    int m = (l+r)>>1;
    init(i*2, l, m), init(i*2+1, m+1, r);
}

void propagate(int i, int l, int r){
    tree[i] = min(tree[i], lazy[i]);
    if(l!=r){
        lazy[i*2] = min(lazy[i*2], lazy[i]);
        lazy[i*2+1] = min(lazy[i*2+1], lazy[i]);
    }
    lazy[i] = 1e9;
}

void rangeMin(int i, int l, int r, int s, int e, int val){
    propagate(i, l, r);
    if(r<s || e<l) return;
    if(s<=l && r<=e){
        lazy[i] = val;
        propagate(i, l, r);
        return;
    }
    int m = (l+r)>>1;
    rangeMin(i*2, l, m, s, e, val);
    rangeMin(i*2+1, m+1, r, s, e, val);
    tree[i] = min(tree[i*2], tree[i*2+1]);
}

int getVal(int i, int l, int r, int idx){
    propagate(i, l, r);
    if(l==r) return tree[i];
    int m = (l+r)>>1;
    if(idx <= m) return getVal(i*2, l, m, idx);
    return getVal(i*2+1, m+1, r, idx);
}

int n, k;
int ans[300002];
vector<ll> xVec;
map<ll, int> mp;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        ll x, y, r;
        scanf("%lld %lld %lld", &x, &y, &r);
        vec.push_back(Circle(x, y, r, i));
        xVec.push_back(x-r), xVec.push_back(x+r);
    }
    sort(vec.begin(), vec.end());
    for(int i=0; i<n; i++){
        indexes[i] = vec[i].idx;
    }

    sort(xVec.begin(), xVec.end());
    xVec.erase(unique(xVec.begin(), xVec.end()), xVec.end());
    for(int i=0; i<(int)xVec.size(); i++) mp[xVec[i]] = i;
    k = (int)xVec.size();

    init(1, 0, k-1);
    for(int i=0; i<n; i++){
        Circle c = vec[i];
        int t1 = getVal(1, 0, k-1, mp[c.x-c.r]);
        int t2 = getVal(1, 0, k-1, mp[c.x+c.r]);
        if(t1 == 1e9 && t2 == 1e9){
            ans[c.idx] = c.idx;
            rangeMin(1, 0, k-1, mp[c.x-c.r], mp[c.x+c.r], i);
        }
        else{
            ans[c.idx] = vec[min(t1, t2)].idx;
        }
    }

    for(int i=1; i<=n; i++) printf("%d ", ans[i]);
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
circle_selection.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |         scanf("%lld %lld %lld", &x, &y, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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