oj.uz

Submission #272717

# Submission time Handle Problem Language Result Execution time Memory
272717 2020-08-18T14:01:36 Z MKopchev Circle selection (APIO18_circle_selection) C++14
87 / 100
 3000 ms 378124 KB 
#include<bits/stdc++.h>
using namespace std;
const int nmax=3e5+42,inf=1e9+42,MX=(1<<20)+42;

struct circle
{
    int x,y,r,id;
};

int n;
circle inp[nmax],sorted_inp[nmax],other_sorted[nmax];

bool touch(circle a,circle b)
{
    long long d=1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y);

    long long mx=a.r+b.r;

    mx=mx*mx;

    return d<=mx;
}

bool cmp(circle a,circle b)
{
    if(a.r!=b.r)return a.r>b.r;
    return a.id<b.id;
}

bool cmp_y(circle a,circle b)
{
    if(a.y!=b.y)return a.y<b.y;
    return a.id<b.id;
}
int outp[nmax];

vector< pair<int/*y*/,int/*id*/> > nodes[MX];
vector<int> prv[MX];
vector<int> nxt[MX];
vector<int> tree[MX];

void update(int node,int l,int r,int pos,circle cur)
{
    //cout<<node<<" -> "<<cur.y<<" "<<cur.id<<endl;
    nodes[node].push_back({cur.y,cur.id});

    if(l==r)return;

    int av=(l+r)/2;

    if(pos<=av)update(node*2,l,av,pos,cur);
    else update(node*2+1,av+1,r,pos,cur);
}
void build(int where,int node,int l,int r)
{
    while(tree[where].size()<=node)tree[where].push_back(0);
    tree[where][node]=r-l+1;

    if(l==r)return;

    int av=(l+r)/2;

    build(where,node*2,l,av);
    build(where,node*2+1,av+1,r);
}
void sub_tree(int where,int node,int l,int r,int pos)
{
    tree[where][node]--;

    if(l==r)return;

    int av=(l+r)/2;

    if(pos<=av)sub_tree(where,node*2,l,av,pos);
    else sub_tree(where,node*2+1,av+1,r,pos);
}
int query(int where,int node,int l,int r,int lq,int rq)
{
    if(tree[where][node]==0)return -1;

    if(l==r)return l;

    int av=(l+r)/2;

    if(lq<=av)
    {
        int mem=query(where,node*2,l,av,lq,min(av,rq));
        if(mem!=-1)return mem;
    }
    if(av<rq)
    {
        int mem=query(where,node*2+1,av+1,r,max(av+1,lq),rq);
        if(mem!=-1)return mem;
    }
    return -1;
}
int find_first(int where,int start)
{
    return query(where,1,0,nodes[where].size()-1,start,nodes[where].size()-1);
}

int pick(int a,int b)
{
    long long sum=a;
    sum=sum+b;

    if(inf<sum)sum=inf;
    if(-inf>sum)sum=-inf;

    return sum;
}
void match(int node,int l,int r,int lq,int rq,circle cur)
{
    if(tree[node].size()==0)return;

    if(tree[node][1]==0)return;

    if(l==lq&&r==rq)
    {
        int y1=pick(cur.y,-2*cur.r);
        int y2=pick(cur.y,2*cur.r);

        int start=lower_bound(nodes[node].begin(),nodes[node].end(),make_pair(y1,0))-nodes[node].begin();

        if(start==nodes[node].size())return;

        start=find_first(node,start);
        /*
        cout<<"circle "<<l<<" "<<r<<" "<<cur.id<<endl;

        for(auto k:nodes[node])
            cout<<k.first<<" "<<k.second<<"\t";cout<<endl;

        cout<<"y1= "<<y1<<" y2= "<<y2<<" start= "<<start<<endl;
        */
        if(start==-1)return;

        vector<int> to_pop={};

        while(start<nodes[node].size()&&nodes[node][start].first<=y2)
        {
            //cout<<"start= "<<start<<" "<<nodes[node][start].second<<" "<<inp[nodes[node][start].second].x<<" "<<inp[nodes[node][start].second].y<<" "<<inp[nodes[node][start].second].r<<endl;

            if(outp[nodes[node][start].second]==0&&touch(inp[nodes[node][start].second],cur))
            {
                //cout<<"touch "<<nodes[node][start].second<<" "<<cur.id<<" "<<endl;

                outp[nodes[node][start].second]=cur.id;
            }

            if(outp[nodes[node][start].second])to_pop.push_back(start);

            start=nxt[node][start];
        }

        for(auto k:to_pop)
        {
            if(0<=prv[node][k])
            {
                nxt[node][prv[node][k]]=nxt[node][k];
            }
            if(nxt[node][k]<nodes[node].size())
            {
                prv[node][nxt[node][k]]=prv[node][k];
            }

            sub_tree(node,1,0,nodes[node].size()-1,k);
        }

        return;
    }

    int av=(l+r)/2;

    if(lq<=av)match(node*2,l,av,lq,min(av,rq),cur);
    if(av<rq)match(node*2+1,av+1,r,max(av+1,lq),rq,cur);
}

int help_x[nmax];

void push(int which)
{
    outp[sorted_inp[which].id]=sorted_inp[which].id;

    int x1=pick(sorted_inp[which].x,-2*sorted_inp[which].r);
    int x2=pick(sorted_inp[which].x,+2*sorted_inp[which].r);

    int le=lower_bound(help_x+1,help_x+n+1,x1)-help_x;
    int ri=upper_bound(help_x+1,help_x+n+1,x2)-help_x;
    ri--;

    //cout<<"le= "<<le<<" ri= "<<ri<<endl;

    if(le>ri)return;

    match(1,1,n,le,ri,sorted_inp[which]);
}
signed main()
{
    scanf("%i",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%i%i%i",&inp[i].x,&inp[i].y,&inp[i].r);
        inp[i].id=i;
    }

    for(int i=1;i<=n;i++)sorted_inp[i]=inp[i],other_sorted[i]=inp[i];

    sort(other_sorted+1,other_sorted+n+1,cmp_y);

    sort(sorted_inp+1,sorted_inp+n+1,cmp);

    for(int i=1;i<=n;i++)help_x[i]=sorted_inp[i].x;

    sort(help_x+1,help_x+n+1);

    for(int i=1;i<=n;i++)
    {
        int pos=lower_bound(help_x+1,help_x+n+1,other_sorted[i].x)-help_x;

        update(1,1,n,pos,other_sorted[i]);
    }

    for(int i=1;i<MX;i++)
        if(nodes[i].size())
        {
            for(int j=0;j<nodes[i].size();j++)
            {
                prv[i].push_back(j-1);
                nxt[i].push_back(j+1);
            }
            build(i,1,0,nodes[i].size()-1);
        }

    for(int i=1;i<=n;i++)
        if(outp[sorted_inp[i].id]==0)
            push(i);

    for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
    return 0;
}

Compilation message

circle_selection.cpp: In function 'void build(int, int, int, int)':
circle_selection.cpp:56:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |     while(tree[where].size()<=node)tree[where].push_back(0);
      |           ~~~~~~~~~~~~~~~~~~^~~~~~
circle_selection.cpp: In function 'void match(int, int, int, int, int, circle)':
circle_selection.cpp:125:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         if(start==nodes[node].size())return;
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:140:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |         while(start<nodes[node].size()&&nodes[node][start].first<=y2)
      |               ~~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:162:28: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |             if(nxt[node][k]<nodes[node].size())
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:227:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  227 |             for(int j=0;j<nodes[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~
circle_selection.cpp:239:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  239 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |     ^~~
circle_selection.cpp:239:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  239 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |                                                ^~~~~~
circle_selection.cpp:200:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  200 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
circle_selection.cpp:203:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  203 |         scanf("%i%i%i",&inp[i].x,&inp[i].y,&inp[i].r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 98936 KB Output is correct
2 Correct 74 ms 98904 KB Output is correct
3 Correct 69 ms 98808 KB Output is correct
4 Correct 71 ms 98808 KB Output is correct
5 Correct 70 ms 98808 KB Output is correct
6 Correct 72 ms 98936 KB Output is correct
7 Correct 70 ms 98936 KB Output is correct
8 Correct 84 ms 98936 KB Output is correct
9 Correct 69 ms 98936 KB Output is correct
10 Correct 85 ms 98936 KB Output is correct
11 Correct 85 ms 98936 KB Output is correct
12 Correct 84 ms 98936 KB Output is correct
13 Correct 72 ms 99056 KB Output is correct
14 Correct 85 ms 98936 KB Output is correct
15 Correct 84 ms 98936 KB Output is correct
16 Correct 87 ms 99320 KB Output is correct
17 Correct 72 ms 99320 KB Output is correct
18 Correct 72 ms 99320 KB Output is correct
19 Correct 91 ms 102376 KB Output is correct
20 Correct 86 ms 102392 KB Output is correct
21 Correct 85 ms 102400 KB Output is correct
22 Correct 108 ms 102392 KB Output is correct
23 Correct 106 ms 102392 KB Output is correct
24 Correct 89 ms 102392 KB Output is correct
25 Correct 92 ms 102392 KB Output is correct
26 Correct 89 ms 102392 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1848 ms 376264 KB Output is correct
2 Correct 1783 ms 376912 KB Output is correct
3 Correct 1635 ms 377292 KB Output is correct
4 Correct 1671 ms 376144 KB Output is correct
5 Correct 1560 ms 360524 KB Output is correct
6 Correct 1792 ms 374956 KB Output is correct
7 Correct 1811 ms 372848 KB Output is correct
8 Correct 1830 ms 374052 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 98936 KB Output is correct
2 Correct 831 ms 173792 KB Output is correct
3 Correct 2743 ms 375252 KB Output is correct
4 Correct 2749 ms 377128 KB Output is correct
5 Correct 2526 ms 369488 KB Output is correct
6 Correct 1089 ms 235252 KB Output is correct
7 Correct 523 ms 166368 KB Output is correct
8 Correct 139 ms 112308 KB Output is correct
9 Correct 2445 ms 373020 KB Output is correct
10 Correct 2478 ms 375372 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2410 ms 377196 KB Output is correct
2 Correct 2120 ms 374980 KB Output is correct
3 Correct 1810 ms 375120 KB Output is correct
4 Correct 2235 ms 375660 KB Output is correct
5 Correct 2075 ms 375072 KB Output is correct
6 Correct 1619 ms 374476 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 98936 KB Output is correct
2 Correct 74 ms 98904 KB Output is correct
3 Correct 69 ms 98808 KB Output is correct
4 Correct 71 ms 98808 KB Output is correct
5 Correct 70 ms 98808 KB Output is correct
6 Correct 72 ms 98936 KB Output is correct
7 Correct 70 ms 98936 KB Output is correct
8 Correct 84 ms 98936 KB Output is correct
9 Correct 69 ms 98936 KB Output is correct
10 Correct 85 ms 98936 KB Output is correct
11 Correct 85 ms 98936 KB Output is correct
12 Correct 84 ms 98936 KB Output is correct
13 Correct 72 ms 99056 KB Output is correct
14 Correct 85 ms 98936 KB Output is correct
15 Correct 84 ms 98936 KB Output is correct
16 Correct 87 ms 99320 KB Output is correct
17 Correct 72 ms 99320 KB Output is correct
18 Correct 72 ms 99320 KB Output is correct
19 Correct 91 ms 102376 KB Output is correct
20 Correct 86 ms 102392 KB Output is correct
21 Correct 85 ms 102400 KB Output is correct
22 Correct 108 ms 102392 KB Output is correct
23 Correct 106 ms 102392 KB Output is correct
24 Correct 89 ms 102392 KB Output is correct
25 Correct 92 ms 102392 KB Output is correct
26 Correct 89 ms 102392 KB Output is correct
27 Correct 104 ms 106256 KB Output is correct
28 Correct 123 ms 106232 KB Output is correct
29 Correct 103 ms 106232 KB Output is correct
30 Correct 113 ms 106232 KB Output is correct
31 Correct 112 ms 106232 KB Output is correct
32 Correct 118 ms 106308 KB Output is correct
33 Correct 541 ms 174180 KB Output is correct
34 Correct 507 ms 173924 KB Output is correct
35 Correct 514 ms 174216 KB Output is correct
36 Correct 743 ms 173560 KB Output is correct
37 Correct 707 ms 173796 KB Output is correct
38 Correct 746 ms 173640 KB Output is correct
39 Correct 524 ms 160096 KB Output is correct
40 Correct 537 ms 160352 KB Output is correct
41 Correct 542 ms 160028 KB Output is correct
42 Correct 397 ms 156900 KB Output is correct
43 Correct 532 ms 173668 KB Output is correct
44 Correct 550 ms 173540 KB Output is correct
45 Correct 536 ms 173540 KB Output is correct
46 Correct 544 ms 173664 KB Output is correct
47 Correct 556 ms 173544 KB Output is correct
48 Correct 546 ms 173572 KB Output is correct
49 Correct 547 ms 173844 KB Output is correct
50 Correct 535 ms 173668 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 98936 KB Output is correct
2 Correct 74 ms 98904 KB Output is correct
3 Correct 69 ms 98808 KB Output is correct
4 Correct 71 ms 98808 KB Output is correct
5 Correct 70 ms 98808 KB Output is correct
6 Correct 72 ms 98936 KB Output is correct
7 Correct 70 ms 98936 KB Output is correct
8 Correct 84 ms 98936 KB Output is correct
9 Correct 69 ms 98936 KB Output is correct
10 Correct 85 ms 98936 KB Output is correct
11 Correct 85 ms 98936 KB Output is correct
12 Correct 84 ms 98936 KB Output is correct
13 Correct 72 ms 99056 KB Output is correct
14 Correct 85 ms 98936 KB Output is correct
15 Correct 84 ms 98936 KB Output is correct
16 Correct 87 ms 99320 KB Output is correct
17 Correct 72 ms 99320 KB Output is correct
18 Correct 72 ms 99320 KB Output is correct
19 Correct 91 ms 102376 KB Output is correct
20 Correct 86 ms 102392 KB Output is correct
21 Correct 85 ms 102400 KB Output is correct
22 Correct 108 ms 102392 KB Output is correct
23 Correct 106 ms 102392 KB Output is correct
24 Correct 89 ms 102392 KB Output is correct
25 Correct 92 ms 102392 KB Output is correct
26 Correct 89 ms 102392 KB Output is correct
27 Correct 1848 ms 376264 KB Output is correct
28 Correct 1783 ms 376912 KB Output is correct
29 Correct 1635 ms 377292 KB Output is correct
30 Correct 1671 ms 376144 KB Output is correct
31 Correct 1560 ms 360524 KB Output is correct
32 Correct 1792 ms 374956 KB Output is correct
33 Correct 1811 ms 372848 KB Output is correct
34 Correct 1830 ms 374052 KB Output is correct
35 Correct 73 ms 98936 KB Output is correct
36 Correct 831 ms 173792 KB Output is correct
37 Correct 2743 ms 375252 KB Output is correct
38 Correct 2749 ms 377128 KB Output is correct
39 Correct 2526 ms 369488 KB Output is correct
40 Correct 1089 ms 235252 KB Output is correct
41 Correct 523 ms 166368 KB Output is correct
42 Correct 139 ms 112308 KB Output is correct
43 Correct 2445 ms 373020 KB Output is correct
44 Correct 2478 ms 375372 KB Output is correct
45 Correct 2410 ms 377196 KB Output is correct
46 Correct 2120 ms 374980 KB Output is correct
47 Correct 1810 ms 375120 KB Output is correct
48 Correct 2235 ms 375660 KB Output is correct
49 Correct 2075 ms 375072 KB Output is correct
50 Correct 1619 ms 374476 KB Output is correct
51 Correct 104 ms 106256 KB Output is correct
52 Correct 123 ms 106232 KB Output is correct
53 Correct 103 ms 106232 KB Output is correct
54 Correct 113 ms 106232 KB Output is correct
55 Correct 112 ms 106232 KB Output is correct
56 Correct 118 ms 106308 KB Output is correct
57 Correct 541 ms 174180 KB Output is correct
58 Correct 507 ms 173924 KB Output is correct
59 Correct 514 ms 174216 KB Output is correct
60 Correct 743 ms 173560 KB Output is correct
61 Correct 707 ms 173796 KB Output is correct
62 Correct 746 ms 173640 KB Output is correct
63 Correct 524 ms 160096 KB Output is correct
64 Correct 537 ms 160352 KB Output is correct
65 Correct 542 ms 160028 KB Output is correct
66 Correct 397 ms 156900 KB Output is correct
67 Correct 532 ms 173668 KB Output is correct
68 Correct 550 ms 173540 KB Output is correct
69 Correct 536 ms 173540 KB Output is correct
70 Correct 544 ms 173664 KB Output is correct
71 Correct 556 ms 173544 KB Output is correct
72 Correct 546 ms 173572 KB Output is correct
73 Correct 547 ms 173844 KB Output is correct
74 Correct 535 ms 173668 KB Output is correct
75 Correct 1632 ms 378124 KB Output is correct
76 Correct 1610 ms 377164 KB Output is correct
77 Correct 1610 ms 376108 KB Output is correct
78 Correct 1654 ms 376504 KB Output is correct
79 Correct 1670 ms 375568 KB Output is correct
80 Correct 1617 ms 376312 KB Output is correct
81 Correct 2527 ms 375344 KB Output is correct
82 Correct 2439 ms 375120 KB Output is correct
83 Correct 2407 ms 375080 KB Output is correct
84 Correct 2607 ms 375232 KB Output is correct
85 Correct 2453 ms 375692 KB Output is correct
86 Correct 2440 ms 375492 KB Output is correct
87 Execution timed out 3099 ms 375016 KB Time limit exceeded
88 Halted 0 ms 0 KB -