oj.uz

Submission #272821

# Submission time Handle Problem Language Result Execution time Memory
272821 2020-08-18T15:50:17 Z MKopchev Circle selection (APIO18_circle_selection) C++14
57 / 100
 2007 ms 269132 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 56 ms 74488 KB Output is correct
2 Correct 55 ms 74236 KB Output is correct
3 Correct 56 ms 74232 KB Output is correct
4 Correct 55 ms 74232 KB Output is correct
5 Correct 56 ms 74232 KB Output is correct
6 Correct 56 ms 74232 KB Output is correct
7 Correct 57 ms 74240 KB Output is correct
8 Correct 56 ms 74232 KB Output is correct
9 Correct 58 ms 74232 KB Output is correct
10 Correct 66 ms 74232 KB Output is correct
11 Correct 57 ms 74232 KB Output is correct
12 Correct 55 ms 74360 KB Output is correct
13 Correct 58 ms 74232 KB Output is correct
14 Correct 58 ms 74232 KB Output is correct
15 Correct 60 ms 74360 KB Output is correct
16 Correct 64 ms 74616 KB Output is correct
17 Correct 57 ms 74616 KB Output is correct
18 Correct 57 ms 74616 KB Output is correct
19 Correct 68 ms 76920 KB Output is correct
20 Correct 69 ms 76956 KB Output is correct
21 Correct 68 ms 76920 KB Output is correct
22 Correct 71 ms 76920 KB Output is correct
23 Correct 72 ms 76920 KB Output is correct
24 Correct 70 ms 76844 KB Output is correct
25 Correct 71 ms 76912 KB Output is correct
26 Correct 77 ms 77048 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1257 ms 269132 KB Output is correct
2 Correct 1221 ms 267628 KB Output is correct
3 Correct 1252 ms 267988 KB Output is correct
4 Correct 1204 ms 265424 KB Output is correct
5 Correct 1215 ms 252492 KB Output is correct
6 Correct 1403 ms 263488 KB Output is correct
7 Correct 1275 ms 261708 KB Output is correct
8 Correct 1338 ms 262348 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 74232 KB Output is correct
2 Correct 572 ms 129952 KB Output is correct
3 Correct 1968 ms 263468 KB Output is correct
4 Correct 2007 ms 263616 KB Output is correct
5 Correct 2007 ms 258044 KB Output is correct
6 Correct 918 ms 169704 KB Output is correct
7 Correct 428 ms 123400 KB Output is correct
8 Correct 113 ms 83956 KB Output is correct
9 Correct 1910 ms 261008 KB Output is correct
10 Correct 1950 ms 263476 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1910 ms 261980 KB Output is correct
2 Correct 1558 ms 263096 KB Output is correct
3 Correct 1373 ms 263192 KB Output is correct
4 Correct 1508 ms 263084 KB Output is correct
5 Correct 1515 ms 262724 KB Output is correct
6 Correct 1306 ms 263032 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 74488 KB Output is correct
2 Correct 55 ms 74236 KB Output is correct
3 Correct 56 ms 74232 KB Output is correct
4 Correct 55 ms 74232 KB Output is correct
5 Correct 56 ms 74232 KB Output is correct
6 Correct 56 ms 74232 KB Output is correct
7 Correct 57 ms 74240 KB Output is correct
8 Correct 56 ms 74232 KB Output is correct
9 Correct 58 ms 74232 KB Output is correct
10 Correct 66 ms 74232 KB Output is correct
11 Correct 57 ms 74232 KB Output is correct
12 Correct 55 ms 74360 KB Output is correct
13 Correct 58 ms 74232 KB Output is correct
14 Correct 58 ms 74232 KB Output is correct
15 Correct 60 ms 74360 KB Output is correct
16 Correct 64 ms 74616 KB Output is correct
17 Correct 57 ms 74616 KB Output is correct
18 Correct 57 ms 74616 KB Output is correct
19 Correct 68 ms 76920 KB Output is correct
20 Correct 69 ms 76956 KB Output is correct
21 Correct 68 ms 76920 KB Output is correct
22 Correct 71 ms 76920 KB Output is correct
23 Correct 72 ms 76920 KB Output is correct
24 Correct 70 ms 76844 KB Output is correct
25 Correct 71 ms 76912 KB Output is correct
26 Correct 77 ms 77048 KB Output is correct
27 Correct 81 ms 79992 KB Output is correct
28 Correct 94 ms 79864 KB Output is correct
29 Correct 87 ms 79888 KB Output is correct
30 Correct 92 ms 79720 KB Output is correct
31 Correct 85 ms 79736 KB Output is correct
32 Correct 85 ms 79736 KB Output is correct
33 Correct 437 ms 129508 KB Output is correct
34 Correct 422 ms 129636 KB Output is correct
35 Correct 416 ms 129928 KB Output is correct
36 Correct 517 ms 129284 KB Output is correct
37 Correct 512 ms 129380 KB Output is correct
38 Correct 564 ms 129508 KB Output is correct
39 Correct 430 ms 117500 KB Output is correct
40 Incorrect 390 ms 117596 KB Output isn't correct
41 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 74488 KB Output is correct
2 Correct 55 ms 74236 KB Output is correct
3 Correct 56 ms 74232 KB Output is correct
4 Correct 55 ms 74232 KB Output is correct
5 Correct 56 ms 74232 KB Output is correct
6 Correct 56 ms 74232 KB Output is correct
7 Correct 57 ms 74240 KB Output is correct
8 Correct 56 ms 74232 KB Output is correct
9 Correct 58 ms 74232 KB Output is correct
10 Correct 66 ms 74232 KB Output is correct
11 Correct 57 ms 74232 KB Output is correct
12 Correct 55 ms 74360 KB Output is correct
13 Correct 58 ms 74232 KB Output is correct
14 Correct 58 ms 74232 KB Output is correct
15 Correct 60 ms 74360 KB Output is correct
16 Correct 64 ms 74616 KB Output is correct
17 Correct 57 ms 74616 KB Output is correct
18 Correct 57 ms 74616 KB Output is correct
19 Correct 68 ms 76920 KB Output is correct
20 Correct 69 ms 76956 KB Output is correct
21 Correct 68 ms 76920 KB Output is correct
22 Correct 71 ms 76920 KB Output is correct
23 Correct 72 ms 76920 KB Output is correct
24 Correct 70 ms 76844 KB Output is correct
25 Correct 71 ms 76912 KB Output is correct
26 Correct 77 ms 77048 KB Output is correct
27 Correct 1257 ms 269132 KB Output is correct
28 Correct 1221 ms 267628 KB Output is correct
29 Correct 1252 ms 267988 KB Output is correct
30 Correct 1204 ms 265424 KB Output is correct
31 Correct 1215 ms 252492 KB Output is correct
32 Correct 1403 ms 263488 KB Output is correct
33 Correct 1275 ms 261708 KB Output is correct
34 Correct 1338 ms 262348 KB Output is correct
35 Correct 55 ms 74232 KB Output is correct
36 Correct 572 ms 129952 KB Output is correct
37 Correct 1968 ms 263468 KB Output is correct
38 Correct 2007 ms 263616 KB Output is correct
39 Correct 2007 ms 258044 KB Output is correct
40 Correct 918 ms 169704 KB Output is correct
41 Correct 428 ms 123400 KB Output is correct
42 Correct 113 ms 83956 KB Output is correct
43 Correct 1910 ms 261008 KB Output is correct
44 Correct 1950 ms 263476 KB Output is correct
45 Correct 1910 ms 261980 KB Output is correct
46 Correct 1558 ms 263096 KB Output is correct
47 Correct 1373 ms 263192 KB Output is correct
48 Correct 1508 ms 263084 KB Output is correct
49 Correct 1515 ms 262724 KB Output is correct
50 Correct 1306 ms 263032 KB Output is correct
51 Correct 81 ms 79992 KB Output is correct
52 Correct 94 ms 79864 KB Output is correct
53 Correct 87 ms 79888 KB Output is correct
54 Correct 92 ms 79720 KB Output is correct
55 Correct 85 ms 79736 KB Output is correct
56 Correct 85 ms 79736 KB Output is correct
57 Correct 437 ms 129508 KB Output is correct
58 Correct 422 ms 129636 KB Output is correct
59 Correct 416 ms 129928 KB Output is correct
60 Correct 517 ms 129284 KB Output is correct
61 Correct 512 ms 129380 KB Output is correct
62 Correct 564 ms 129508 KB Output is correct
63 Correct 430 ms 117500 KB Output is correct
64 Incorrect 390 ms 117596 KB Output isn't correct
65 Halted 0 ms 0 KB -