Submission #60225

#	Time	Username	Problem	Language	Result	Execution time	Memory
60225		duality	Circle selection (APIO18_circle_selection)	C++11	19 / 100	3031 ms	37716 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long int LLI;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;

LLI sq(LLI n) { return n*n; }
struct circle { int x,y,r,i; };
bool comp(circle a,circle b) {
    if (a.r == b.r) return a.i < b.i;
    else return a.r > b.r;
}
circle c[300000];
int ans[300000];
pii sorted[300000];
int arr1[300000],arr2[300000];
int tree1[1 << 20],tree2[1 << 20];
int comp1(int a,int b) {
    if (a == -1) return b;
    else if (b == -1) return a;
    else if (arr1[a] > arr1[b]) return a;
    else return b;
}
int comp2(int a,int b) {
    if (a == -1) return b;
    else if (b == -1) return a;
    else if (arr2[a] > arr2[b]) return a;
    else return b;
}
int build1(int s,int e,int i) {
    if (s == e) {
        tree1[i] = s;
        return 0;
    }

    int mid = (s+e) / 2;
    build1(s,mid,2*i+1),build1(mid+1,e,2*i+2);
    tree1[i] = comp1(tree1[2*i+1],tree1[2*i+2]);
    return 0;
}
int query1(int s,int e,int qs,int qe,int i) {
    if ((s > qe) || (e < qs)) return -1;
    else if ((s >= qs) && (e <= qe)) return tree1[i];

    int mid = (s+e) / 2;
    return comp1(query1(s,mid,qs,qe,2*i+1),query1(mid+1,e,qs,qe,2*i+2));
}
int update1(int s,int e,int ai,int i) {
    if ((s > ai) || (e < ai)) return tree1[i];
    else if (s == e) return tree1[i];

    int mid = (s+e) / 2;
    tree1[i] = comp1(update1(s,mid,ai,2*i+1),update1(mid+1,e,ai,2*i+2));
    return tree1[i];
}
int build2(int s,int e,int i) {
    if (s == e) {
        tree2[i] = s;
        return 0;
    }

    int mid = (s+e) / 2;
    build2(s,mid,2*i+1),build2(mid+1,e,2*i+2);
    tree2[i] = comp2(tree2[2*i+1],tree2[2*i+2]);
    return 0;
}
int query2(int s,int e,int qs,int qe,int i) {
    if ((s > qe) || (e < qs)) return -1;
    else if ((s >= qs) && (e <= qe)) return tree2[i];

    int mid = (s+e) / 2;
    return comp2(query2(s,mid,qs,qe,2*i+1),query2(mid+1,e,qs,qe,2*i+2));
}
int update2(int s,int e,int ai,int i) {
    if ((s > ai) || (e < ai)) return tree2[i];
    else if (s == e) return tree2[i];

    int mid = (s+e) / 2;
    tree2[i] = comp2(update2(s,mid,ai,2*i+1),update2(mid+1,e,ai,2*i+2));
    return tree2[i];
}
int main() {
    int i;
    int n;
    int sub2 = 1;
    scanf("%d",&n);
    for (i = 0; i < n; i++) scanf("%d %d %d",&c[i].x,&c[i].y,&c[i].r),c[i].i = i,sub2 &= (c[i].y == 0);
    sort(c,c+n,comp);

    int j;
    if (sub2) {
        fill(ans,ans+n,-1);
        for (i = 0; i < n; i++) sorted[i] = mp(c[i].x,c[i].i);
        sort(sorted,sorted+n);
        for (i = 0; i < n; i++) {
            int p = lower_bound(sorted,sorted+n,mp(c[i].x,c[i].i))-sorted;
            arr1[p] = c[i].x+c[i].r,arr2[p] = c[i].r-c[i].x;
        }
        build1(0,n-1,0),build2(0,n-1,0);
        //for (i=0;i<7;i++)cout<<tree1[i];
        //for (i=0;i<7;i++)cout<<tree2[i];
        //cout<<endl;
        fill(ans,ans+n,-1);
        for (i = 0; i < n; i++) {
            if (ans[c[i].i] == -1) {
                while (1) {
                    int p = upper_bound(sorted,sorted+n,mp(c[i].x,n))-sorted-1;
                    //cout<<"p: "<<p<<endl;
                    p = query1(0,n-1,0,p,0);
                    if (arr1[p] >= c[i].x-c[i].r) {
                        arr1[p] = -2e9;
                        if (ans[sorted[p].second] == -1) ans[sorted[p].second] = c[i].i;
                        update1(0,n-1,p,0);
                    }
                    else {
                        p = lower_bound(sorted,sorted+n,mp(c[i].x,0))-sorted;
                        p = query2(0,n-1,p,n-1,0);
                        if (arr2[p] >= -(c[i].x+c[i].r)) {
                            arr2[p] = -2e9;
                            if (ans[sorted[p].second] == -1) ans[sorted[p].second] = c[i].i;
                            update2(0,n-1,p,0);
                        }
                        else break;
                    }
                }
                //for (j=0;j<7;j++)cout<<tree1[j];
                //cout<<endl;
        //for (j=0;j<7;j++)cout<<tree2[j];
        //cout<<endl;
            }
        }
    }
    else {
        fill(ans,ans+n,-1);
        for (i = 0; i < n; i++) {
            if (ans[c[i].i] == -1) {
                for (j = 0; j < n; j++) {
                    if (ans[c[j].i] == -1) {
                        if (sq(c[i].x-c[j].x)+sq(c[i].y-c[j].y) <= sq(c[i].r+c[j].r)) ans[c[j].i] = c[i].i;
                    }
                }
            }
        }
    }
    for (i = 0; i < n; i++) printf("%d ",ans[i]+1);

    return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
circle_selection.cpp:90:81: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < n; i++) scanf("%d %d %d",&c[i].x,&c[i].y,&c[i].r),c[i].i = i,sub2 &= (c[i].y == 0);
                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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