Submission #298900

#	Time	Username	Problem	Language	Result	Execution time	Memory
298900		mhy908	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3084 ms	391132 KiB

circle_selection

#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
const int INF=1e9;
const LL LLINF=1e18;

vector<int> vc;
//struct SEGMENT_TREE{
    set<pii> ss[2400010];
    void update(int point, int s, int e, int num, pii val, bool ad){
        if(ad)ss[point].insert(val);
        else ss[point].erase(val);
        if(s==e)return;
        if(num<=(s+e)/2)update(point*2, s, (s+e)/2, num, val, ad);
        else update(point*2+1, (s+e)/2+1, e, num, val, ad);
    }
    void query(int point, int s, int e, int sx, int ex, int sy, int ey){
        if(e<sx||s>ex)return;
        if(sx<=s&&e<=ex){
            auto it=ss[point].lower_bound(mp(sy, 0));
            while(it!=ss[point].end()){
                if(it->F>ey)break;
                vc.eb(it->S);
                it++;
            }
            return;
        }
        query(point*2, s, (s+e)/2, sx, ex, sy, ey);
        query(point*2+1, (s+e)/2+1, e, sx, ex, sy, ey);
    }
//}seg;

int n, ans[300010], l[300010], r[300010];
pair<pii, pii> arr[300010];
vector<int> idx;
bool cmp(pair<pii, pii> a, pair<pii, pii> b){return mp(a.S.F, -a.S.S)>mp(b.S.F, -b.S.S);}
bool is_con(int a, int b){
    LL d=(LL)(arr[a].F.F-arr[b].F.F)*(arr[a].F.F-arr[b].F.F)+(LL)(arr[a].F.S-arr[b].F.S)*(arr[a].F.S-arr[b].F.S);
    LL rs=(LL)(arr[a].S.F+arr[b].S.F)*(arr[a].S.F+arr[b].S.F);
    return rs>=d;
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d %d %d", &arr[i].F.F, &arr[i].F.S, &arr[i].S.F);
        idx.eb(arr[i].F.F-arr[i].S.F);
        idx.eb(arr[i].F.F+arr[i].S.F);
        arr[i].S.S=i;
    }
    sort(arr+1, arr+n+1, cmp);
    svec(idx); press(idx);
    for(int i=1; i<=n; i++){
        l[i]=lower_bound(all(idx), arr[i].F.F-arr[i].S.F)-idx.begin()+1;
        r[i]=lower_bound(all(idx), arr[i].F.F+arr[i].S.F)-idx.begin()+1;
        update(1, 1, idx.size(), l[i], mp(arr[i].F.S-arr[i].S.F, i), 1);
        update(1, 1, idx.size(), l[i], mp(arr[i].F.S+arr[i].S.F, i), 1);
        update(1, 1, idx.size(), r[i], mp(arr[i].F.S-arr[i].S.F, i), 1);
        update(1, 1, idx.size(), r[i], mp(arr[i].F.S+arr[i].S.F, i), 1);
    }
    for(int i=1; i<=n; i++){
        if(ans[arr[i].S.S])continue;
        query(1, 1, idx.size(), l[i], r[i], arr[i].F.S-arr[i].S.F, arr[i].F.S+arr[i].S.F);
        //svec(vc); press(vc);
        //printf("%d : ", arr[i].S.S);
        for(auto j:vc){
            if(ans[arr[j].S.S])continue;
            //printf("%d ", arr[j].S.S);
            if(is_con(i, j)){
                ans[arr[j].S.S]=arr[i].S.S;
                update(1, 1, idx.size(), l[j], mp(arr[j].F.S-arr[j].S.F, j), 0);
                update(1, 1, idx.size(), l[j], mp(arr[j].F.S+arr[j].S.F, j), 0);
                update(1, 1, idx.size(), r[j], mp(arr[j].F.S-arr[j].S.F, j), 0);
                update(1, 1, idx.size(), r[j], mp(arr[j].F.S+arr[j].S.F, j), 0);
            }
        }
        //puts("");
        vc.clear();
    }
    for(int i=1; i<=n; i++)printf("%d ", ans[i]);
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
circle_selection.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |         scanf("%d %d %d", &arr[i].F.F, &arr[i].F.S, &arr[i].S.F);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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