oj.uz

Submission #272796

# Submission time Handle Problem Language Result Execution time Memory
272796 2020-08-18T15:33:27 Z MKopchev Circle selection (APIO18_circle_selection) C++14
87 / 100
 3000 ms 425984 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];
vector<int> fenwick[MX];
vector<int> on[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 SZ[nmax];

void upd(int where,int j,int val)
{
    if(val==-1)on[where][j]=0;

    j++;

    while(j<=SZ[nodes[where].size()])
    {
        fenwick[where][j-1]+=val;
        j=j+(j&(-j));
    }
}

int LST_SEEN[nmax];

void build(int where)
{
    for(int i=0;i<=SZ[nodes[where].size()]-1;i++)
    {
        fenwick[where].push_back(0);
        on[where].push_back(1);
    }

    if(LST_SEEN[nodes[where].size()])
    {
        for(int j=1;j<=SZ[nodes[where].size()];j++)fenwick[where][j-1]=fenwick[LST_SEEN[nodes[where].size()]][j-1];
    }
    else
    {
        for(int i=0;i<nodes[where].size();i++)
            upd(where,i,1);
    }

    LST_SEEN[nodes[where].size()]=where;
}
void sub_tree(int where,int pos)
{
    upd(where,pos,-1);
}

int query(int where,int pos)
{
    pos++;

    int ret=0;

    while(pos)
    {
        ret=ret+fenwick[where][pos-1];
        pos=pos-(pos&(-pos));
    }
    return ret;
}

int bits[nmax];

int find_first(int where,int start)
{
    if(on[where][start])return start;

    int sum=query(where,start-1);

    //cout<<"find_first "<<where<<" "<<start<<" "<<sum<<endl;

    if(sum==fenwick[where][SZ[nodes[where].size()]-1])return -1;

    int pos=0;

    for(int j=bits[nodes[where].size()]-1;j>=0;j--)
        if(fenwick[where][pos+(1<<j)-1]<=sum)
        {
            sum=sum-fenwick[where][pos+(1<<j)-1];
            pos=pos+(1<<j);
        }

    //cout<<"pos= "<<pos<<endl;

    return pos;
}

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(fenwick[node].size()==0)return;

    if(fenwick[node][SZ[nodes[node].size()]-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,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]);
    }

    int st=0;
    for(int i=1;i<=n;i++)
    {
        if((1<<st)<i)st++;

        SZ[i]=1<<st;

        bits[i]=st;

        //cout<<i<<" -> "<<SZ[i]<<" "<<bits[i]<<endl;
    }
    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);
        }

    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)':
circle_selection.cpp:91: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]
   91 |         for(int i=0;i<nodes[where].size();i++)
      |                     ~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp: In function 'void match(int, int, int, int, int, circle)':
circle_selection.cpp:166: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]
  166 |         if(start==nodes[node].size())return;
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:181: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]
  181 |         while(start<nodes[node].size()&&nodes[node][start].first<=y2)
      |               ~~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:203: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]
  203 |             if(nxt[node][k]<nodes[node].size())
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:279: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]
  279 |             for(int j=0;j<nodes[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~
circle_selection.cpp:291:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  291 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |     ^~~
circle_selection.cpp:291:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  291 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |                                                ^~~~~~
circle_selection.cpp:241:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  241 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
circle_selection.cpp:244:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  244 |         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 83 ms 123512 KB Output is correct
2 Correct 85 ms 123676 KB Output is correct
3 Correct 89 ms 123512 KB Output is correct
4 Correct 91 ms 123640 KB Output is correct
5 Correct 84 ms 123512 KB Output is correct
6 Correct 85 ms 123516 KB Output is correct
7 Correct 88 ms 123512 KB Output is correct
8 Correct 88 ms 123512 KB Output is correct
9 Correct 96 ms 123512 KB Output is correct
10 Correct 83 ms 123488 KB Output is correct
11 Correct 91 ms 123488 KB Output is correct
12 Correct 86 ms 123512 KB Output is correct
13 Correct 85 ms 123512 KB Output is correct
14 Correct 84 ms 123512 KB Output is correct
15 Correct 86 ms 123512 KB Output is correct
16 Correct 90 ms 124152 KB Output is correct
17 Correct 90 ms 124152 KB Output is correct
18 Correct 95 ms 124024 KB Output is correct
19 Correct 100 ms 127480 KB Output is correct
20 Correct 102 ms 127480 KB Output is correct
21 Correct 100 ms 127608 KB Output is correct
22 Correct 105 ms 127480 KB Output is correct
23 Correct 105 ms 127480 KB Output is correct
24 Correct 104 ms 127480 KB Output is correct
25 Correct 105 ms 127480 KB Output is correct
26 Correct 105 ms 127480 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1565 ms 418540 KB Output is correct
2 Correct 1594 ms 423776 KB Output is correct
3 Correct 1638 ms 423952 KB Output is correct
4 Correct 1568 ms 422804 KB Output is correct
5 Correct 1643 ms 401912 KB Output is correct
6 Correct 1904 ms 420384 KB Output is correct
7 Correct 1729 ms 417900 KB Output is correct
8 Correct 1685 ms 419308 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 123512 KB Output is correct
2 Correct 835 ms 207068 KB Output is correct
3 Correct 2671 ms 424192 KB Output is correct
4 Correct 2765 ms 424516 KB Output is correct
5 Correct 2513 ms 417612 KB Output is correct
6 Correct 1171 ms 272436 KB Output is correct
7 Correct 626 ms 198116 KB Output is correct
8 Correct 181 ms 138364 KB Output is correct
9 Correct 2497 ms 422040 KB Output is correct
10 Correct 2451 ms 424052 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2575 ms 424360 KB Output is correct
2 Correct 2256 ms 422856 KB Output is correct
3 Correct 1801 ms 423904 KB Output is correct
4 Correct 2361 ms 423872 KB Output is correct
5 Correct 2206 ms 423652 KB Output is correct
6 Correct 1610 ms 423512 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 123512 KB Output is correct
2 Correct 85 ms 123676 KB Output is correct
3 Correct 89 ms 123512 KB Output is correct
4 Correct 91 ms 123640 KB Output is correct
5 Correct 84 ms 123512 KB Output is correct
6 Correct 85 ms 123516 KB Output is correct
7 Correct 88 ms 123512 KB Output is correct
8 Correct 88 ms 123512 KB Output is correct
9 Correct 96 ms 123512 KB Output is correct
10 Correct 83 ms 123488 KB Output is correct
11 Correct 91 ms 123488 KB Output is correct
12 Correct 86 ms 123512 KB Output is correct
13 Correct 85 ms 123512 KB Output is correct
14 Correct 84 ms 123512 KB Output is correct
15 Correct 86 ms 123512 KB Output is correct
16 Correct 90 ms 124152 KB Output is correct
17 Correct 90 ms 124152 KB Output is correct
18 Correct 95 ms 124024 KB Output is correct
19 Correct 100 ms 127480 KB Output is correct
20 Correct 102 ms 127480 KB Output is correct
21 Correct 100 ms 127608 KB Output is correct
22 Correct 105 ms 127480 KB Output is correct
23 Correct 105 ms 127480 KB Output is correct
24 Correct 104 ms 127480 KB Output is correct
25 Correct 105 ms 127480 KB Output is correct
26 Correct 105 ms 127480 KB Output is correct
27 Correct 124 ms 131832 KB Output is correct
28 Correct 128 ms 131960 KB Output is correct
29 Correct 126 ms 131836 KB Output is correct
30 Correct 135 ms 131712 KB Output is correct
31 Correct 145 ms 131704 KB Output is correct
32 Correct 134 ms 131704 KB Output is correct
33 Correct 537 ms 207624 KB Output is correct
34 Correct 519 ms 207588 KB Output is correct
35 Correct 572 ms 207624 KB Output is correct
36 Correct 801 ms 206688 KB Output is correct
37 Correct 716 ms 206936 KB Output is correct
38 Correct 739 ms 206900 KB Output is correct
39 Correct 536 ms 186592 KB Output is correct
40 Correct 539 ms 186720 KB Output is correct
41 Correct 531 ms 186468 KB Output is correct
42 Correct 406 ms 184092 KB Output is correct
43 Correct 586 ms 206720 KB Output is correct
44 Correct 585 ms 206692 KB Output is correct
45 Correct 613 ms 206748 KB Output is correct
46 Correct 625 ms 206708 KB Output is correct
47 Correct 632 ms 206820 KB Output is correct
48 Correct 624 ms 206636 KB Output is correct
49 Correct 568 ms 206688 KB Output is correct
50 Correct 576 ms 206608 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 123512 KB Output is correct
2 Correct 85 ms 123676 KB Output is correct
3 Correct 89 ms 123512 KB Output is correct
4 Correct 91 ms 123640 KB Output is correct
5 Correct 84 ms 123512 KB Output is correct
6 Correct 85 ms 123516 KB Output is correct
7 Correct 88 ms 123512 KB Output is correct
8 Correct 88 ms 123512 KB Output is correct
9 Correct 96 ms 123512 KB Output is correct
10 Correct 83 ms 123488 KB Output is correct
11 Correct 91 ms 123488 KB Output is correct
12 Correct 86 ms 123512 KB Output is correct
13 Correct 85 ms 123512 KB Output is correct
14 Correct 84 ms 123512 KB Output is correct
15 Correct 86 ms 123512 KB Output is correct
16 Correct 90 ms 124152 KB Output is correct
17 Correct 90 ms 124152 KB Output is correct
18 Correct 95 ms 124024 KB Output is correct
19 Correct 100 ms 127480 KB Output is correct
20 Correct 102 ms 127480 KB Output is correct
21 Correct 100 ms 127608 KB Output is correct
22 Correct 105 ms 127480 KB Output is correct
23 Correct 105 ms 127480 KB Output is correct
24 Correct 104 ms 127480 KB Output is correct
25 Correct 105 ms 127480 KB Output is correct
26 Correct 105 ms 127480 KB Output is correct
27 Correct 1565 ms 418540 KB Output is correct
28 Correct 1594 ms 423776 KB Output is correct
29 Correct 1638 ms 423952 KB Output is correct
30 Correct 1568 ms 422804 KB Output is correct
31 Correct 1643 ms 401912 KB Output is correct
32 Correct 1904 ms 420384 KB Output is correct
33 Correct 1729 ms 417900 KB Output is correct
34 Correct 1685 ms 419308 KB Output is correct
35 Correct 98 ms 123512 KB Output is correct
36 Correct 835 ms 207068 KB Output is correct
37 Correct 2671 ms 424192 KB Output is correct
38 Correct 2765 ms 424516 KB Output is correct
39 Correct 2513 ms 417612 KB Output is correct
40 Correct 1171 ms 272436 KB Output is correct
41 Correct 626 ms 198116 KB Output is correct
42 Correct 181 ms 138364 KB Output is correct
43 Correct 2497 ms 422040 KB Output is correct
44 Correct 2451 ms 424052 KB Output is correct
45 Correct 2575 ms 424360 KB Output is correct
46 Correct 2256 ms 422856 KB Output is correct
47 Correct 1801 ms 423904 KB Output is correct
48 Correct 2361 ms 423872 KB Output is correct
49 Correct 2206 ms 423652 KB Output is correct
50 Correct 1610 ms 423512 KB Output is correct
51 Correct 124 ms 131832 KB Output is correct
52 Correct 128 ms 131960 KB Output is correct
53 Correct 126 ms 131836 KB Output is correct
54 Correct 135 ms 131712 KB Output is correct
55 Correct 145 ms 131704 KB Output is correct
56 Correct 134 ms 131704 KB Output is correct
57 Correct 537 ms 207624 KB Output is correct
58 Correct 519 ms 207588 KB Output is correct
59 Correct 572 ms 207624 KB Output is correct
60 Correct 801 ms 206688 KB Output is correct
61 Correct 716 ms 206936 KB Output is correct
62 Correct 739 ms 206900 KB Output is correct
63 Correct 536 ms 186592 KB Output is correct
64 Correct 539 ms 186720 KB Output is correct
65 Correct 531 ms 186468 KB Output is correct
66 Correct 406 ms 184092 KB Output is correct
67 Correct 586 ms 206720 KB Output is correct
68 Correct 585 ms 206692 KB Output is correct
69 Correct 613 ms 206748 KB Output is correct
70 Correct 625 ms 206708 KB Output is correct
71 Correct 632 ms 206820 KB Output is correct
72 Correct 624 ms 206636 KB Output is correct
73 Correct 568 ms 206688 KB Output is correct
74 Correct 576 ms 206608 KB Output is correct
75 Correct 1645 ms 425252 KB Output is correct
76 Correct 1584 ms 425984 KB Output is correct
77 Correct 1600 ms 424868 KB Output is correct
78 Correct 1642 ms 424920 KB Output is correct
79 Correct 1639 ms 424392 KB Output is correct
80 Correct 1625 ms 424680 KB Output is correct
81 Correct 2676 ms 424284 KB Output is correct
82 Correct 2765 ms 423956 KB Output is correct
83 Correct 2566 ms 424028 KB Output is correct
84 Correct 2741 ms 424508 KB Output is correct
85 Correct 2666 ms 424116 KB Output is correct
86 Correct 2789 ms 424264 KB Output is correct
87 Execution timed out 3122 ms 423876 KB Time limit exceeded
88 Halted 0 ms 0 KB -