oj.uz

Submission #272781

# Submission time Handle Problem Language Result Execution time Memory
272781 2020-08-18T15:27:49 Z MKopchev Circle selection (APIO18_circle_selection) C++14
87 / 100
 3000 ms 357592 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];

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

    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)
{
    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],pointer=0;

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+pointer+1,x1)-help_x;
    int ri=upper_bound(help_x+1,help_x+pointer+1,x2)-help_x;
    ri--;

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

    if(le>ri)return;

    match(1,1,pointer,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);

    set<int> x={};

    for(int i=1;i<=n;i++)
        if(x.count(sorted_inp[i].x)==0)
        {
            pointer++;
            help_x[pointer]=sorted_inp[i].x;
            x.insert(help_x[pointer]);

            //cout<<"pointer= "<<pointer<<" "<<help_x[pointer]<<endl;
        }

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

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

        update(1,1,pointer,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:84: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]
   84 |         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:157: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]
  157 |         if(start==nodes[node].size())return;
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:172: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]
  172 |         while(start<nodes[node].size()&&nodes[node][start].first<=y2)
      |               ~~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:194: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]
  194 |             if(nxt[node][k]<nodes[node].size())
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:281: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]
  281 |             for(int j=0;j<nodes[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~
circle_selection.cpp:293:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  293 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |     ^~~
circle_selection.cpp:293:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  293 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |                                                ^~~~~~
circle_selection.cpp:232:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  232 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
circle_selection.cpp:235:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  235 |         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 98928 KB Output is correct
2 Correct 81 ms 98808 KB Output is correct
3 Correct 78 ms 98808 KB Output is correct
4 Correct 82 ms 98808 KB Output is correct
5 Correct 80 ms 98808 KB Output is correct
6 Correct 81 ms 98936 KB Output is correct
7 Correct 85 ms 98936 KB Output is correct
8 Correct 85 ms 98936 KB Output is correct
9 Correct 73 ms 98936 KB Output is correct
10 Correct 115 ms 98868 KB Output is correct
11 Correct 80 ms 98964 KB Output is correct
12 Correct 83 ms 98844 KB Output is correct
13 Correct 92 ms 98936 KB Output is correct
14 Correct 91 ms 98936 KB Output is correct
15 Correct 91 ms 98912 KB Output is correct
16 Correct 93 ms 99448 KB Output is correct
17 Correct 73 ms 99424 KB Output is correct
18 Correct 75 ms 99320 KB Output is correct
19 Correct 102 ms 102392 KB Output is correct
20 Correct 118 ms 102392 KB Output is correct
21 Correct 104 ms 102372 KB Output is correct
22 Correct 115 ms 102264 KB Output is correct
23 Correct 106 ms 102308 KB Output is correct
24 Correct 100 ms 102392 KB Output is correct
25 Correct 119 ms 102352 KB Output is correct
26 Correct 103 ms 102352 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2057 ms 355228 KB Output is correct
2 Correct 1862 ms 356888 KB Output is correct
3 Correct 1801 ms 356684 KB Output is correct
4 Correct 1672 ms 355660 KB Output is correct
5 Correct 1527 ms 320488 KB Output is correct
6 Correct 1981 ms 354380 KB Output is correct
7 Correct 2004 ms 347400 KB Output is correct
8 Correct 1848 ms 350756 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 98936 KB Output is correct
2 Correct 791 ms 171552 KB Output is correct
3 Correct 2844 ms 354908 KB Output is correct
4 Correct 2965 ms 354960 KB Output is correct
5 Correct 2746 ms 348712 KB Output is correct
6 Correct 1139 ms 226520 KB Output is correct
7 Correct 528 ms 163176 KB Output is correct
8 Correct 140 ms 111988 KB Output is correct
9 Correct 2588 ms 352812 KB Output is correct
10 Correct 2524 ms 355520 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2652 ms 354788 KB Output is correct
2 Correct 2317 ms 355012 KB Output is correct
3 Correct 1932 ms 355452 KB Output is correct
4 Correct 2462 ms 354904 KB Output is correct
5 Correct 2578 ms 354760 KB Output is correct
6 Correct 1898 ms 354384 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 98928 KB Output is correct
2 Correct 81 ms 98808 KB Output is correct
3 Correct 78 ms 98808 KB Output is correct
4 Correct 82 ms 98808 KB Output is correct
5 Correct 80 ms 98808 KB Output is correct
6 Correct 81 ms 98936 KB Output is correct
7 Correct 85 ms 98936 KB Output is correct
8 Correct 85 ms 98936 KB Output is correct
9 Correct 73 ms 98936 KB Output is correct
10 Correct 115 ms 98868 KB Output is correct
11 Correct 80 ms 98964 KB Output is correct
12 Correct 83 ms 98844 KB Output is correct
13 Correct 92 ms 98936 KB Output is correct
14 Correct 91 ms 98936 KB Output is correct
15 Correct 91 ms 98912 KB Output is correct
16 Correct 93 ms 99448 KB Output is correct
17 Correct 73 ms 99424 KB Output is correct
18 Correct 75 ms 99320 KB Output is correct
19 Correct 102 ms 102392 KB Output is correct
20 Correct 118 ms 102392 KB Output is correct
21 Correct 104 ms 102372 KB Output is correct
22 Correct 115 ms 102264 KB Output is correct
23 Correct 106 ms 102308 KB Output is correct
24 Correct 100 ms 102392 KB Output is correct
25 Correct 119 ms 102352 KB Output is correct
26 Correct 103 ms 102352 KB Output is correct
27 Correct 107 ms 106360 KB Output is correct
28 Correct 105 ms 106360 KB Output is correct
29 Correct 106 ms 106360 KB Output is correct
30 Correct 116 ms 106236 KB Output is correct
31 Correct 119 ms 106232 KB Output is correct
32 Correct 114 ms 106236 KB Output is correct
33 Correct 499 ms 171748 KB Output is correct
34 Correct 506 ms 171964 KB Output is correct
35 Correct 512 ms 172168 KB Output is correct
36 Correct 707 ms 171492 KB Output is correct
37 Correct 714 ms 171428 KB Output is correct
38 Correct 775 ms 171620 KB Output is correct
39 Correct 383 ms 132964 KB Output is correct
40 Correct 366 ms 132964 KB Output is correct
41 Correct 364 ms 132708 KB Output is correct
42 Correct 261 ms 131940 KB Output is correct
43 Correct 587 ms 171268 KB Output is correct
44 Correct 584 ms 171240 KB Output is correct
45 Correct 585 ms 171360 KB Output is correct
46 Correct 591 ms 171448 KB Output is correct
47 Correct 571 ms 171256 KB Output is correct
48 Correct 594 ms 171364 KB Output is correct
49 Correct 594 ms 171240 KB Output is correct
50 Correct 598 ms 171364 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 98928 KB Output is correct
2 Correct 81 ms 98808 KB Output is correct
3 Correct 78 ms 98808 KB Output is correct
4 Correct 82 ms 98808 KB Output is correct
5 Correct 80 ms 98808 KB Output is correct
6 Correct 81 ms 98936 KB Output is correct
7 Correct 85 ms 98936 KB Output is correct
8 Correct 85 ms 98936 KB Output is correct
9 Correct 73 ms 98936 KB Output is correct
10 Correct 115 ms 98868 KB Output is correct
11 Correct 80 ms 98964 KB Output is correct
12 Correct 83 ms 98844 KB Output is correct
13 Correct 92 ms 98936 KB Output is correct
14 Correct 91 ms 98936 KB Output is correct
15 Correct 91 ms 98912 KB Output is correct
16 Correct 93 ms 99448 KB Output is correct
17 Correct 73 ms 99424 KB Output is correct
18 Correct 75 ms 99320 KB Output is correct
19 Correct 102 ms 102392 KB Output is correct
20 Correct 118 ms 102392 KB Output is correct
21 Correct 104 ms 102372 KB Output is correct
22 Correct 115 ms 102264 KB Output is correct
23 Correct 106 ms 102308 KB Output is correct
24 Correct 100 ms 102392 KB Output is correct
25 Correct 119 ms 102352 KB Output is correct
26 Correct 103 ms 102352 KB Output is correct
27 Correct 2057 ms 355228 KB Output is correct
28 Correct 1862 ms 356888 KB Output is correct
29 Correct 1801 ms 356684 KB Output is correct
30 Correct 1672 ms 355660 KB Output is correct
31 Correct 1527 ms 320488 KB Output is correct
32 Correct 1981 ms 354380 KB Output is correct
33 Correct 2004 ms 347400 KB Output is correct
34 Correct 1848 ms 350756 KB Output is correct
35 Correct 78 ms 98936 KB Output is correct
36 Correct 791 ms 171552 KB Output is correct
37 Correct 2844 ms 354908 KB Output is correct
38 Correct 2965 ms 354960 KB Output is correct
39 Correct 2746 ms 348712 KB Output is correct
40 Correct 1139 ms 226520 KB Output is correct
41 Correct 528 ms 163176 KB Output is correct
42 Correct 140 ms 111988 KB Output is correct
43 Correct 2588 ms 352812 KB Output is correct
44 Correct 2524 ms 355520 KB Output is correct
45 Correct 2652 ms 354788 KB Output is correct
46 Correct 2317 ms 355012 KB Output is correct
47 Correct 1932 ms 355452 KB Output is correct
48 Correct 2462 ms 354904 KB Output is correct
49 Correct 2578 ms 354760 KB Output is correct
50 Correct 1898 ms 354384 KB Output is correct
51 Correct 107 ms 106360 KB Output is correct
52 Correct 105 ms 106360 KB Output is correct
53 Correct 106 ms 106360 KB Output is correct
54 Correct 116 ms 106236 KB Output is correct
55 Correct 119 ms 106232 KB Output is correct
56 Correct 114 ms 106236 KB Output is correct
57 Correct 499 ms 171748 KB Output is correct
58 Correct 506 ms 171964 KB Output is correct
59 Correct 512 ms 172168 KB Output is correct
60 Correct 707 ms 171492 KB Output is correct
61 Correct 714 ms 171428 KB Output is correct
62 Correct 775 ms 171620 KB Output is correct
63 Correct 383 ms 132964 KB Output is correct
64 Correct 366 ms 132964 KB Output is correct
65 Correct 364 ms 132708 KB Output is correct
66 Correct 261 ms 131940 KB Output is correct
67 Correct 587 ms 171268 KB Output is correct
68 Correct 584 ms 171240 KB Output is correct
69 Correct 585 ms 171360 KB Output is correct
70 Correct 591 ms 171448 KB Output is correct
71 Correct 571 ms 171256 KB Output is correct
72 Correct 594 ms 171364 KB Output is correct
73 Correct 594 ms 171240 KB Output is correct
74 Correct 598 ms 171364 KB Output is correct
75 Correct 1903 ms 356552 KB Output is correct
76 Correct 1978 ms 357068 KB Output is correct
77 Correct 1820 ms 357280 KB Output is correct
78 Correct 1871 ms 357232 KB Output is correct
79 Correct 1946 ms 356476 KB Output is correct
80 Correct 1895 ms 357592 KB Output is correct
81 Correct 2670 ms 356544 KB Output is correct
82 Correct 2628 ms 357064 KB Output is correct
83 Correct 2743 ms 356840 KB Output is correct
84 Correct 2909 ms 356644 KB Output is correct
85 Correct 2766 ms 356760 KB Output is correct
86 Correct 2655 ms 356700 KB Output is correct
87 Execution timed out 3078 ms 354588 KB Time limit exceeded
88 Halted 0 ms 0 KB -