Submission #49078

#	Time	Username	Problem	Language	Result	Execution time	Memory
49078		yusufake	Circle selection (APIO18_circle_selection)	C++98	87 / 100	3052 ms	28760 KiB

circle_selection

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

#define mp make_pair 
#define pb push_back 
#define st first 
#define nd second 

typedef long long ll; 
typedef pair < int , int > pp; 
const int mod = 1e9 + 7; 
const int N   = 3e5 + 5; 

struct node{
    int id, mn[2];
    node *l, *r;
    node(int i) { l = r = NULL; id = i; }
};

int p[N][2],A[N],B[N],tmp[N],R[N],ans[N],r;

node* bld(int l, int r, int k){
    if(l > r) return NULL;
    int *X = k ? B : A;
    int *Y = k ? A : B;
    int i,j,jj, m = l+r >> 1;
    int mid = p[ X[m] ][k];
    for(; m>l && mid == p[ X[m-1] ][k] ; m--);
    node *root = new node(X[m]);
    root->mn[0] = A[l];
    root->mn[1] = B[l];
    for(j=l-1,jj=m,i=l;i<=r;i++){
        if(p[ Y[i] ][k] < mid)
            tmp[++j] = Y[i];
        else if(Y[i] != X[m])
            tmp[++jj] = Y[i];
    }
    for(i=l;i<=r;i++) Y[i] = tmp[i]; 
    root -> l = bld(l,m-1,!k);
    root -> r = bld(m+1,r,!k);
    return root;
}

node* del(node* root, int i, int k){
    if(root == NULL) assert(0);
    if(root->id == i){
        if(root -> r != NULL){
            int j = root->r->mn[k];
            root->id = j;
            root->r = del(root->r, j, !k);
        }   
        else if(root -> l != NULL){
            int j = root->l->mn[k];
            root->id = j;  root->r = root->l;  root->l = NULL;
            root->r = del(root->r, j, !k);
        }
        else return NULL;
    }
    else{
        if(p[i][k] < p[ root->id ][k]) root->l = del(root->l, i, !k);
        else root->r = del(root->r, i, !k);
    }
    
    root->mn[k] = root->l ? root->l->mn[k] : root->id;
    root->mn[!k] = root->id;
    if(root->l != NULL && p[ root->l->mn[!k] ][!k] < p[ root->mn[!k] ][!k]) root->mn[!k] = root->l->mn[!k];
    if(root->r != NULL && p[ root->r->mn[!k] ][!k] < p[ root->mn[!k] ][!k]) root->mn[!k] = root->r->mn[!k];
    return root;
}

vector < int > era;
void f(node* root, int q[], int k){
	if(root == NULL) return;
    ll a = q[0] - p[ root->id ][0];
    ll b = q[1] - p[ root->id ][1];
    ll c = R[ root->id ];
	if(a*a + b*b <= (r+c)*(r+c))
		era.pb(root->id);
    int t = p[ root->id ][k];
	if(q[k] < t){
		f(root->l,q,!k);
		if(t - q[k] <= r+r) f(root->r,q,!k); 
	}
	else{
		f(root->r,q,!k);
		if(q[k] - t <= r+r) f(root->l,q,!k); 
	}
}

int h;
bool cmp(int i, int j){
    return p[i][h] < p[j][h];
}

int n,i,j;
pp T[N];
int main()
{
    cin >> n;
    for(i=1;i<=n;i++) { scanf("%d%d%d",&p[i][0],&p[i][1],&R[i]); A[i] = B[i] = i; }
    h=0; sort(A+1,A+n+1,cmp);
    h=1; sort(B+1,B+n+1,cmp);
    node *root = bld(1,n,0);

    for(i=1;i<=n;i++) T[i] = mp(-R[i] , i);
    sort(T+1 , T+n+1);
    for(i=1;i<=n;i++){
        int id = T[i].nd;
        if(ans[id]) continue;
        era.clear();
        r = R[id];
   		f(root , p[id], 0);
   		for(auto j : era){
            ans[j] = id;
            root = del(root, j, 0);
        }
    }

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

Compilation message (stderr)

circle_selection.cpp: In function 'node* bld(int, int, int)':
circle_selection.cpp:26:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int i,j,jj, m = l+r >> 1;
                     ~^~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:100:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++) { scanf("%d%d%d",&p[i][0],&p[i][1],&R[i]); A[i] = B[i] = i; }
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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