oj.uz

Submission #272840

# Submission time Handle Problem Language Result Execution time Memory
272840 2020-08-18T16:04:30 Z MKopchev Circle selection (APIO18_circle_selection) C++14
57 / 100
 2040 ms 264384 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize ("unroll-loops")

#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];

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);
}

int find_first(int where,int start)
{
    if(start>=nodes[where].size())return -1;

    if(nxt[where][start]==-1)return -1;

    if(outp[nodes[where][start].second]==0)return start;

    nxt[where][start]=find_first(where,nxt[where][start]);

    return nxt[where][start];
}

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(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();

        //cout<<"start_try= "<<start<<endl;

        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];
            }
        }

        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);
            }
        }

    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 'int find_first(int, int)':
circle_selection.cpp:60:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     if(start>=nodes[where].size())return -1;
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp: In function 'void match(int, int, int, int, int, circle)':
circle_selection.cpp:93: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]
   93 |         if(start==nodes[node].size())return;
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:108: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]
  108 |         while(start<nodes[node].size()&&nodes[node][start].first<=y2)
      |               ~~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:130: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]
  130 |             if(nxt[node][k]<nodes[node].size())
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:192: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]
  192 |             for(int j=0;j<nodes[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~
circle_selection.cpp:203:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  203 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |     ^~~
circle_selection.cpp:203:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  203 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |                                                ^~~~~~
circle_selection.cpp:166:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  166 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
circle_selection.cpp:169:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  169 |         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 55 ms 74232 KB Output is correct
2 Correct 50 ms 74360 KB Output is correct
3 Correct 51 ms 74232 KB Output is correct
4 Correct 49 ms 74232 KB Output is correct
5 Correct 50 ms 74232 KB Output is correct
6 Correct 50 ms 74232 KB Output is correct
7 Correct 57 ms 74232 KB Output is correct
8 Correct 50 ms 74232 KB Output is correct
9 Correct 57 ms 74232 KB Output is correct
10 Correct 52 ms 74232 KB Output is correct
11 Correct 50 ms 74232 KB Output is correct
12 Correct 52 ms 74232 KB Output is correct
13 Correct 50 ms 74240 KB Output is correct
14 Correct 51 ms 74232 KB Output is correct
15 Correct 53 ms 74360 KB Output is correct
16 Correct 52 ms 74616 KB Output is correct
17 Correct 52 ms 74624 KB Output is correct
18 Correct 53 ms 74592 KB Output is correct
19 Correct 62 ms 76792 KB Output is correct
20 Correct 61 ms 76792 KB Output is correct
21 Correct 62 ms 76792 KB Output is correct
22 Correct 63 ms 76792 KB Output is correct
23 Correct 67 ms 76792 KB Output is correct
24 Correct 63 ms 76792 KB Output is correct
25 Correct 62 ms 76668 KB Output is correct
26 Correct 62 ms 76792 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1238 ms 262504 KB Output is correct
2 Correct 1233 ms 264140 KB Output is correct
3 Correct 1236 ms 264384 KB Output is correct
4 Correct 1338 ms 262284 KB Output is correct
5 Correct 1307 ms 250464 KB Output is correct
6 Correct 1418 ms 261100 KB Output is correct
7 Correct 1305 ms 259324 KB Output is correct
8 Correct 1458 ms 260096 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 74232 KB Output is correct
2 Correct 627 ms 127200 KB Output is correct
3 Correct 1997 ms 261464 KB Output is correct
4 Correct 2001 ms 261704 KB Output is correct
5 Correct 1886 ms 256104 KB Output is correct
6 Correct 823 ms 167512 KB Output is correct
7 Correct 389 ms 121200 KB Output is correct
8 Correct 100 ms 83448 KB Output is correct
9 Correct 1908 ms 259132 KB Output is correct
10 Correct 2040 ms 261132 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1987 ms 261984 KB Output is correct
2 Correct 1586 ms 261056 KB Output is correct
3 Correct 1481 ms 260900 KB Output is correct
4 Correct 1623 ms 261220 KB Output is correct
5 Correct 1576 ms 261064 KB Output is correct
6 Correct 1417 ms 260556 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 74232 KB Output is correct
2 Correct 50 ms 74360 KB Output is correct
3 Correct 51 ms 74232 KB Output is correct
4 Correct 49 ms 74232 KB Output is correct
5 Correct 50 ms 74232 KB Output is correct
6 Correct 50 ms 74232 KB Output is correct
7 Correct 57 ms 74232 KB Output is correct
8 Correct 50 ms 74232 KB Output is correct
9 Correct 57 ms 74232 KB Output is correct
10 Correct 52 ms 74232 KB Output is correct
11 Correct 50 ms 74232 KB Output is correct
12 Correct 52 ms 74232 KB Output is correct
13 Correct 50 ms 74240 KB Output is correct
14 Correct 51 ms 74232 KB Output is correct
15 Correct 53 ms 74360 KB Output is correct
16 Correct 52 ms 74616 KB Output is correct
17 Correct 52 ms 74624 KB Output is correct
18 Correct 53 ms 74592 KB Output is correct
19 Correct 62 ms 76792 KB Output is correct
20 Correct 61 ms 76792 KB Output is correct
21 Correct 62 ms 76792 KB Output is correct
22 Correct 63 ms 76792 KB Output is correct
23 Correct 67 ms 76792 KB Output is correct
24 Correct 63 ms 76792 KB Output is correct
25 Correct 62 ms 76668 KB Output is correct
26 Correct 62 ms 76792 KB Output is correct
27 Correct 74 ms 79608 KB Output is correct
28 Correct 86 ms 79608 KB Output is correct
29 Correct 90 ms 79556 KB Output is correct
30 Correct 88 ms 79480 KB Output is correct
31 Correct 84 ms 79480 KB Output is correct
32 Correct 83 ms 79480 KB Output is correct
33 Correct 392 ms 127328 KB Output is correct
34 Correct 401 ms 127584 KB Output is correct
35 Correct 394 ms 127756 KB Output is correct
36 Correct 594 ms 127100 KB Output is correct
37 Correct 540 ms 127076 KB Output is correct
38 Correct 574 ms 127036 KB Output is correct
39 Correct 417 ms 116332 KB Output is correct
40 Incorrect 438 ms 116676 KB Output isn't correct
41 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 74232 KB Output is correct
2 Correct 50 ms 74360 KB Output is correct
3 Correct 51 ms 74232 KB Output is correct
4 Correct 49 ms 74232 KB Output is correct
5 Correct 50 ms 74232 KB Output is correct
6 Correct 50 ms 74232 KB Output is correct
7 Correct 57 ms 74232 KB Output is correct
8 Correct 50 ms 74232 KB Output is correct
9 Correct 57 ms 74232 KB Output is correct
10 Correct 52 ms 74232 KB Output is correct
11 Correct 50 ms 74232 KB Output is correct
12 Correct 52 ms 74232 KB Output is correct
13 Correct 50 ms 74240 KB Output is correct
14 Correct 51 ms 74232 KB Output is correct
15 Correct 53 ms 74360 KB Output is correct
16 Correct 52 ms 74616 KB Output is correct
17 Correct 52 ms 74624 KB Output is correct
18 Correct 53 ms 74592 KB Output is correct
19 Correct 62 ms 76792 KB Output is correct
20 Correct 61 ms 76792 KB Output is correct
21 Correct 62 ms 76792 KB Output is correct
22 Correct 63 ms 76792 KB Output is correct
23 Correct 67 ms 76792 KB Output is correct
24 Correct 63 ms 76792 KB Output is correct
25 Correct 62 ms 76668 KB Output is correct
26 Correct 62 ms 76792 KB Output is correct
27 Correct 1238 ms 262504 KB Output is correct
28 Correct 1233 ms 264140 KB Output is correct
29 Correct 1236 ms 264384 KB Output is correct
30 Correct 1338 ms 262284 KB Output is correct
31 Correct 1307 ms 250464 KB Output is correct
32 Correct 1418 ms 261100 KB Output is correct
33 Correct 1305 ms 259324 KB Output is correct
34 Correct 1458 ms 260096 KB Output is correct
35 Correct 54 ms 74232 KB Output is correct
36 Correct 627 ms 127200 KB Output is correct
37 Correct 1997 ms 261464 KB Output is correct
38 Correct 2001 ms 261704 KB Output is correct
39 Correct 1886 ms 256104 KB Output is correct
40 Correct 823 ms 167512 KB Output is correct
41 Correct 389 ms 121200 KB Output is correct
42 Correct 100 ms 83448 KB Output is correct
43 Correct 1908 ms 259132 KB Output is correct
44 Correct 2040 ms 261132 KB Output is correct
45 Correct 1987 ms 261984 KB Output is correct
46 Correct 1586 ms 261056 KB Output is correct
47 Correct 1481 ms 260900 KB Output is correct
48 Correct 1623 ms 261220 KB Output is correct
49 Correct 1576 ms 261064 KB Output is correct
50 Correct 1417 ms 260556 KB Output is correct
51 Correct 74 ms 79608 KB Output is correct
52 Correct 86 ms 79608 KB Output is correct
53 Correct 90 ms 79556 KB Output is correct
54 Correct 88 ms 79480 KB Output is correct
55 Correct 84 ms 79480 KB Output is correct
56 Correct 83 ms 79480 KB Output is correct
57 Correct 392 ms 127328 KB Output is correct
58 Correct 401 ms 127584 KB Output is correct
59 Correct 394 ms 127756 KB Output is correct
60 Correct 594 ms 127100 KB Output is correct
61 Correct 540 ms 127076 KB Output is correct
62 Correct 574 ms 127036 KB Output is correct
63 Correct 417 ms 116332 KB Output is correct
64 Incorrect 438 ms 116676 KB Output isn't correct
65 Halted 0 ms 0 KB -