oj.uz

Submission #272848

# Submission time Handle Problem Language Result Execution time Memory
272848 2020-08-18T16:15:38 Z MKopchev Circle selection (APIO18_circle_selection) C++14
57 / 100
 2221 ms 264736 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);

        int start_slow=start;

        while(start_slow<nodes[node].size()&&outp[nodes[node][start_slow].second])start_slow++;

        if(start_slow==nodes[node].size())start_slow=-1;

        //assert(start==start_slow);

        start=start_slow;

        /*
        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:99:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         while(start_slow<nodes[node].size()&&outp[nodes[node][start_slow].second])start_slow++;
      |               ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:101:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         if(start_slow==nodes[node].size())start_slow=-1;
      |            ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:119: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]
  119 |         while(start<nodes[node].size()&&nodes[node][start].first<=y2)
      |               ~~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:141: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]
  141 |             if(nxt[node][k]<nodes[node].size())
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:203: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]
  203 |             for(int j=0;j<nodes[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~
circle_selection.cpp:214:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  214 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |     ^~~
circle_selection.cpp:214:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  214 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |                                                ^~~~~~
circle_selection.cpp:177:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  177 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
circle_selection.cpp:180:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  180 |         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 50 ms 74232 KB Output is correct
2 Correct 67 ms 74232 KB Output is correct
3 Correct 60 ms 74232 KB Output is correct
4 Correct 62 ms 74368 KB Output is correct
5 Correct 58 ms 74240 KB Output is correct
6 Correct 59 ms 74360 KB Output is correct
7 Correct 53 ms 74240 KB Output is correct
8 Correct 52 ms 74232 KB Output is correct
9 Correct 53 ms 74232 KB Output is correct
10 Correct 52 ms 74232 KB Output is correct
11 Correct 52 ms 74232 KB Output is correct
12 Correct 55 ms 74360 KB Output is correct
13 Correct 52 ms 74236 KB Output is correct
14 Correct 52 ms 74240 KB Output is correct
15 Correct 52 ms 74232 KB Output is correct
16 Correct 61 ms 74616 KB Output is correct
17 Correct 58 ms 74616 KB Output is correct
18 Correct 56 ms 74612 KB Output is correct
19 Correct 71 ms 76920 KB Output is correct
20 Correct 63 ms 76792 KB Output is correct
21 Correct 63 ms 76792 KB Output is correct
22 Correct 75 ms 76792 KB Output is correct
23 Correct 77 ms 76796 KB Output is correct
24 Correct 68 ms 76792 KB Output is correct
25 Correct 67 ms 76792 KB Output is correct
26 Correct 65 ms 76792 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1167 ms 262640 KB Output is correct
2 Correct 1206 ms 264524 KB Output is correct
3 Correct 1452 ms 264736 KB Output is correct
4 Correct 1386 ms 262612 KB Output is correct
5 Correct 1264 ms 250528 KB Output is correct
6 Correct 1379 ms 261492 KB Output is correct
7 Correct 1214 ms 259876 KB Output is correct
8 Correct 1308 ms 260400 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 74232 KB Output is correct
2 Correct 626 ms 127456 KB Output is correct
3 Correct 2106 ms 261652 KB Output is correct
4 Correct 1997 ms 261960 KB Output is correct
5 Correct 1895 ms 256580 KB Output is correct
6 Correct 846 ms 167848 KB Output is correct
7 Correct 402 ms 121316 KB Output is correct
8 Correct 110 ms 83572 KB Output is correct
9 Correct 2221 ms 259412 KB Output is correct
10 Correct 2000 ms 261948 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2084 ms 262764 KB Output is correct
2 Correct 1529 ms 261964 KB Output is correct
3 Correct 1410 ms 261828 KB Output is correct
4 Correct 1571 ms 262100 KB Output is correct
5 Correct 1508 ms 261836 KB Output is correct
6 Correct 1291 ms 261396 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 74232 KB Output is correct
2 Correct 67 ms 74232 KB Output is correct
3 Correct 60 ms 74232 KB Output is correct
4 Correct 62 ms 74368 KB Output is correct
5 Correct 58 ms 74240 KB Output is correct
6 Correct 59 ms 74360 KB Output is correct
7 Correct 53 ms 74240 KB Output is correct
8 Correct 52 ms 74232 KB Output is correct
9 Correct 53 ms 74232 KB Output is correct
10 Correct 52 ms 74232 KB Output is correct
11 Correct 52 ms 74232 KB Output is correct
12 Correct 55 ms 74360 KB Output is correct
13 Correct 52 ms 74236 KB Output is correct
14 Correct 52 ms 74240 KB Output is correct
15 Correct 52 ms 74232 KB Output is correct
16 Correct 61 ms 74616 KB Output is correct
17 Correct 58 ms 74616 KB Output is correct
18 Correct 56 ms 74612 KB Output is correct
19 Correct 71 ms 76920 KB Output is correct
20 Correct 63 ms 76792 KB Output is correct
21 Correct 63 ms 76792 KB Output is correct
22 Correct 75 ms 76792 KB Output is correct
23 Correct 77 ms 76796 KB Output is correct
24 Correct 68 ms 76792 KB Output is correct
25 Correct 67 ms 76792 KB Output is correct
26 Correct 65 ms 76792 KB Output is correct
27 Correct 80 ms 79864 KB Output is correct
28 Correct 83 ms 79992 KB Output is correct
29 Correct 82 ms 79864 KB Output is correct
30 Correct 94 ms 79784 KB Output is correct
31 Correct 88 ms 79736 KB Output is correct
32 Correct 87 ms 79736 KB Output is correct
33 Correct 389 ms 128224 KB Output is correct
34 Correct 400 ms 128204 KB Output is correct
35 Correct 400 ms 128520 KB Output is correct
36 Correct 540 ms 127580 KB Output is correct
37 Correct 599 ms 127840 KB Output is correct
38 Correct 580 ms 127844 KB Output is correct
39 Correct 431 ms 116704 KB Output is correct
40 Incorrect 487 ms 116828 KB Output isn't correct
41 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 74232 KB Output is correct
2 Correct 67 ms 74232 KB Output is correct
3 Correct 60 ms 74232 KB Output is correct
4 Correct 62 ms 74368 KB Output is correct
5 Correct 58 ms 74240 KB Output is correct
6 Correct 59 ms 74360 KB Output is correct
7 Correct 53 ms 74240 KB Output is correct
8 Correct 52 ms 74232 KB Output is correct
9 Correct 53 ms 74232 KB Output is correct
10 Correct 52 ms 74232 KB Output is correct
11 Correct 52 ms 74232 KB Output is correct
12 Correct 55 ms 74360 KB Output is correct
13 Correct 52 ms 74236 KB Output is correct
14 Correct 52 ms 74240 KB Output is correct
15 Correct 52 ms 74232 KB Output is correct
16 Correct 61 ms 74616 KB Output is correct
17 Correct 58 ms 74616 KB Output is correct
18 Correct 56 ms 74612 KB Output is correct
19 Correct 71 ms 76920 KB Output is correct
20 Correct 63 ms 76792 KB Output is correct
21 Correct 63 ms 76792 KB Output is correct
22 Correct 75 ms 76792 KB Output is correct
23 Correct 77 ms 76796 KB Output is correct
24 Correct 68 ms 76792 KB Output is correct
25 Correct 67 ms 76792 KB Output is correct
26 Correct 65 ms 76792 KB Output is correct
27 Correct 1167 ms 262640 KB Output is correct
28 Correct 1206 ms 264524 KB Output is correct
29 Correct 1452 ms 264736 KB Output is correct
30 Correct 1386 ms 262612 KB Output is correct
31 Correct 1264 ms 250528 KB Output is correct
32 Correct 1379 ms 261492 KB Output is correct
33 Correct 1214 ms 259876 KB Output is correct
34 Correct 1308 ms 260400 KB Output is correct
35 Correct 60 ms 74232 KB Output is correct
36 Correct 626 ms 127456 KB Output is correct
37 Correct 2106 ms 261652 KB Output is correct
38 Correct 1997 ms 261960 KB Output is correct
39 Correct 1895 ms 256580 KB Output is correct
40 Correct 846 ms 167848 KB Output is correct
41 Correct 402 ms 121316 KB Output is correct
42 Correct 110 ms 83572 KB Output is correct
43 Correct 2221 ms 259412 KB Output is correct
44 Correct 2000 ms 261948 KB Output is correct
45 Correct 2084 ms 262764 KB Output is correct
46 Correct 1529 ms 261964 KB Output is correct
47 Correct 1410 ms 261828 KB Output is correct
48 Correct 1571 ms 262100 KB Output is correct
49 Correct 1508 ms 261836 KB Output is correct
50 Correct 1291 ms 261396 KB Output is correct
51 Correct 80 ms 79864 KB Output is correct
52 Correct 83 ms 79992 KB Output is correct
53 Correct 82 ms 79864 KB Output is correct
54 Correct 94 ms 79784 KB Output is correct
55 Correct 88 ms 79736 KB Output is correct
56 Correct 87 ms 79736 KB Output is correct
57 Correct 389 ms 128224 KB Output is correct
58 Correct 400 ms 128204 KB Output is correct
59 Correct 400 ms 128520 KB Output is correct
60 Correct 540 ms 127580 KB Output is correct
61 Correct 599 ms 127840 KB Output is correct
62 Correct 580 ms 127844 KB Output is correct
63 Correct 431 ms 116704 KB Output is correct
64 Incorrect 487 ms 116828 KB Output isn't correct
65 Halted 0 ms 0 KB -