oj.uz

Submission #60224

# Submission time Handle Problem Language Result Execution time Memory
60224 2018-07-23T21:50:14 Z duality Circle selection (APIO18_circle_selection) C++11
7 / 100
 3000 ms 46264 KB 
#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));
}
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));
}
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

circle_selection.cpp: In function 'int update1(int, int, int, int)':
circle_selection.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
circle_selection.cpp: In function 'int update2(int, int, int, int)':
circle_selection.cpp:82:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
circle_selection.cpp:88: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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 688 KB Output is correct
9 Correct 4 ms 688 KB Output is correct
10 Correct 3 ms 688 KB Output is correct
11 Correct 3 ms 688 KB Output is correct
12 Correct 3 ms 688 KB Output is correct
13 Correct 3 ms 688 KB Output is correct
14 Correct 3 ms 688 KB Output is correct
15 Correct 3 ms 688 KB Output is correct
16 Correct 5 ms 688 KB Output is correct
17 Correct 5 ms 828 KB Output is correct
18 Correct 4 ms 828 KB Output is correct
19 Correct 7 ms 1020 KB Output is correct
20 Correct 8 ms 1164 KB Output is correct
21 Correct 9 ms 1328 KB Output is correct
22 Correct 55 ms 1372 KB Output is correct
23 Correct 50 ms 1608 KB Output is correct
24 Correct 76 ms 1864 KB Output is correct
25 Correct 54 ms 1892 KB Output is correct
26 Correct 57 ms 2148 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 390 ms 46264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 46264 KB Output is correct
2 Execution timed out 3090 ms 46264 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3044 ms 46264 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 688 KB Output is correct
9 Correct 4 ms 688 KB Output is correct
10 Correct 3 ms 688 KB Output is correct
11 Correct 3 ms 688 KB Output is correct
12 Correct 3 ms 688 KB Output is correct
13 Correct 3 ms 688 KB Output is correct
14 Correct 3 ms 688 KB Output is correct
15 Correct 3 ms 688 KB Output is correct
16 Correct 5 ms 688 KB Output is correct
17 Correct 5 ms 828 KB Output is correct
18 Correct 4 ms 828 KB Output is correct
19 Correct 7 ms 1020 KB Output is correct
20 Correct 8 ms 1164 KB Output is correct
21 Correct 9 ms 1328 KB Output is correct
22 Correct 55 ms 1372 KB Output is correct
23 Correct 50 ms 1608 KB Output is correct
24 Correct 76 ms 1864 KB Output is correct
25 Correct 54 ms 1892 KB Output is correct
26 Correct 57 ms 2148 KB Output is correct
27 Correct 10 ms 46264 KB Output is correct
28 Correct 10 ms 46264 KB Output is correct
29 Correct 12 ms 46264 KB Output is correct
30 Correct 284 ms 46264 KB Output is correct
31 Correct 217 ms 46264 KB Output is correct
32 Correct 224 ms 46264 KB Output is correct
33 Correct 108 ms 46264 KB Output is correct
34 Correct 100 ms 46264 KB Output is correct
35 Correct 110 ms 46264 KB Output is correct
36 Execution timed out 3030 ms 46264 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 688 KB Output is correct
9 Correct 4 ms 688 KB Output is correct
10 Correct 3 ms 688 KB Output is correct
11 Correct 3 ms 688 KB Output is correct
12 Correct 3 ms 688 KB Output is correct
13 Correct 3 ms 688 KB Output is correct
14 Correct 3 ms 688 KB Output is correct
15 Correct 3 ms 688 KB Output is correct
16 Correct 5 ms 688 KB Output is correct
17 Correct 5 ms 828 KB Output is correct
18 Correct 4 ms 828 KB Output is correct
19 Correct 7 ms 1020 KB Output is correct
20 Correct 8 ms 1164 KB Output is correct
21 Correct 9 ms 1328 KB Output is correct
22 Correct 55 ms 1372 KB Output is correct
23 Correct 50 ms 1608 KB Output is correct
24 Correct 76 ms 1864 KB Output is correct
25 Correct 54 ms 1892 KB Output is correct
26 Correct 57 ms 2148 KB Output is correct
27 Runtime error 390 ms 46264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Halted 0 ms 0 KB -