oj.uz

Submission #272771

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

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: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:270: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]
  270 |             for(int j=0;j<nodes[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~
circle_selection.cpp:282:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  282 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |     ^~~
circle_selection.cpp:282:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  282 |     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 98808 KB Output is correct
2 Correct 69 ms 98808 KB Output is correct
3 Correct 69 ms 98808 KB Output is correct
4 Correct 70 ms 98940 KB Output is correct
5 Correct 76 ms 98808 KB Output is correct
6 Correct 70 ms 98936 KB Output is correct
7 Correct 71 ms 98936 KB Output is correct
8 Correct 71 ms 98936 KB Output is correct
9 Correct 72 ms 98908 KB Output is correct
10 Correct 80 ms 98936 KB Output is correct
11 Correct 70 ms 98936 KB Output is correct
12 Correct 71 ms 98936 KB Output is correct
13 Correct 71 ms 99016 KB Output is correct
14 Correct 71 ms 98936 KB Output is correct
15 Correct 70 ms 98936 KB Output is correct
16 Correct 73 ms 99320 KB Output is correct
17 Correct 75 ms 99300 KB Output is correct
18 Correct 86 ms 99448 KB Output is correct
19 Correct 86 ms 102168 KB Output is correct
20 Correct 87 ms 102136 KB Output is correct
21 Correct 89 ms 102136 KB Output is correct
22 Correct 90 ms 102008 KB Output is correct
23 Correct 100 ms 102008 KB Output is correct
24 Correct 87 ms 102008 KB Output is correct
25 Correct 88 ms 102012 KB Output is correct
26 Correct 87 ms 102008 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1388 ms 340940 KB Output is correct
2 Correct 1378 ms 341448 KB Output is correct
3 Correct 1384 ms 341784 KB Output is correct
4 Correct 1377 ms 340800 KB Output is correct
5 Correct 1449 ms 325328 KB Output is correct
6 Correct 1717 ms 339532 KB Output is correct
7 Correct 1449 ms 337244 KB Output is correct
8 Correct 1522 ms 338864 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 98808 KB Output is correct
2 Correct 701 ms 166160 KB Output is correct
3 Correct 2449 ms 339784 KB Output is correct
4 Correct 2472 ms 340812 KB Output is correct
5 Correct 2280 ms 334076 KB Output is correct
6 Correct 1010 ms 218712 KB Output is correct
7 Correct 483 ms 158856 KB Output is correct
8 Correct 134 ms 110964 KB Output is correct
9 Correct 2398 ms 337732 KB Output is correct
10 Correct 2221 ms 339864 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2318 ms 340680 KB Output is correct
2 Correct 2029 ms 339792 KB Output is correct
3 Correct 1655 ms 339652 KB Output is correct
4 Correct 2323 ms 340172 KB Output is correct
5 Correct 2230 ms 339532 KB Output is correct
6 Correct 1615 ms 339008 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 98808 KB Output is correct
2 Correct 69 ms 98808 KB Output is correct
3 Correct 69 ms 98808 KB Output is correct
4 Correct 70 ms 98940 KB Output is correct
5 Correct 76 ms 98808 KB Output is correct
6 Correct 70 ms 98936 KB Output is correct
7 Correct 71 ms 98936 KB Output is correct
8 Correct 71 ms 98936 KB Output is correct
9 Correct 72 ms 98908 KB Output is correct
10 Correct 80 ms 98936 KB Output is correct
11 Correct 70 ms 98936 KB Output is correct
12 Correct 71 ms 98936 KB Output is correct
13 Correct 71 ms 99016 KB Output is correct
14 Correct 71 ms 98936 KB Output is correct
15 Correct 70 ms 98936 KB Output is correct
16 Correct 73 ms 99320 KB Output is correct
17 Correct 75 ms 99300 KB Output is correct
18 Correct 86 ms 99448 KB Output is correct
19 Correct 86 ms 102168 KB Output is correct
20 Correct 87 ms 102136 KB Output is correct
21 Correct 89 ms 102136 KB Output is correct
22 Correct 90 ms 102008 KB Output is correct
23 Correct 100 ms 102008 KB Output is correct
24 Correct 87 ms 102008 KB Output is correct
25 Correct 88 ms 102012 KB Output is correct
26 Correct 87 ms 102008 KB Output is correct
27 Correct 107 ms 105592 KB Output is correct
28 Correct 106 ms 105592 KB Output is correct
29 Correct 102 ms 105592 KB Output is correct
30 Correct 112 ms 105464 KB Output is correct
31 Correct 116 ms 105464 KB Output is correct
32 Correct 108 ms 105464 KB Output is correct
33 Correct 460 ms 166372 KB Output is correct
34 Correct 465 ms 166296 KB Output is correct
35 Correct 473 ms 166516 KB Output is correct
36 Correct 726 ms 166112 KB Output is correct
37 Correct 731 ms 166112 KB Output is correct
38 Correct 713 ms 166120 KB Output is correct
39 Correct 544 ms 151376 KB Output is correct
40 Correct 535 ms 151752 KB Output is correct
41 Correct 503 ms 151168 KB Output is correct
42 Correct 370 ms 148704 KB Output is correct
43 Correct 587 ms 165984 KB Output is correct
44 Correct 519 ms 165988 KB Output is correct
45 Correct 560 ms 165988 KB Output is correct
46 Correct 607 ms 166056 KB Output is correct
47 Correct 583 ms 165988 KB Output is correct
48 Correct 593 ms 165988 KB Output is correct
49 Correct 582 ms 165988 KB Output is correct
50 Correct 526 ms 165860 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 98808 KB Output is correct
2 Correct 69 ms 98808 KB Output is correct
3 Correct 69 ms 98808 KB Output is correct
4 Correct 70 ms 98940 KB Output is correct
5 Correct 76 ms 98808 KB Output is correct
6 Correct 70 ms 98936 KB Output is correct
7 Correct 71 ms 98936 KB Output is correct
8 Correct 71 ms 98936 KB Output is correct
9 Correct 72 ms 98908 KB Output is correct
10 Correct 80 ms 98936 KB Output is correct
11 Correct 70 ms 98936 KB Output is correct
12 Correct 71 ms 98936 KB Output is correct
13 Correct 71 ms 99016 KB Output is correct
14 Correct 71 ms 98936 KB Output is correct
15 Correct 70 ms 98936 KB Output is correct
16 Correct 73 ms 99320 KB Output is correct
17 Correct 75 ms 99300 KB Output is correct
18 Correct 86 ms 99448 KB Output is correct
19 Correct 86 ms 102168 KB Output is correct
20 Correct 87 ms 102136 KB Output is correct
21 Correct 89 ms 102136 KB Output is correct
22 Correct 90 ms 102008 KB Output is correct
23 Correct 100 ms 102008 KB Output is correct
24 Correct 87 ms 102008 KB Output is correct
25 Correct 88 ms 102012 KB Output is correct
26 Correct 87 ms 102008 KB Output is correct
27 Correct 1388 ms 340940 KB Output is correct
28 Correct 1378 ms 341448 KB Output is correct
29 Correct 1384 ms 341784 KB Output is correct
30 Correct 1377 ms 340800 KB Output is correct
31 Correct 1449 ms 325328 KB Output is correct
32 Correct 1717 ms 339532 KB Output is correct
33 Correct 1449 ms 337244 KB Output is correct
34 Correct 1522 ms 338864 KB Output is correct
35 Correct 71 ms 98808 KB Output is correct
36 Correct 701 ms 166160 KB Output is correct
37 Correct 2449 ms 339784 KB Output is correct
38 Correct 2472 ms 340812 KB Output is correct
39 Correct 2280 ms 334076 KB Output is correct
40 Correct 1010 ms 218712 KB Output is correct
41 Correct 483 ms 158856 KB Output is correct
42 Correct 134 ms 110964 KB Output is correct
43 Correct 2398 ms 337732 KB Output is correct
44 Correct 2221 ms 339864 KB Output is correct
45 Correct 2318 ms 340680 KB Output is correct
46 Correct 2029 ms 339792 KB Output is correct
47 Correct 1655 ms 339652 KB Output is correct
48 Correct 2323 ms 340172 KB Output is correct
49 Correct 2230 ms 339532 KB Output is correct
50 Correct 1615 ms 339008 KB Output is correct
51 Correct 107 ms 105592 KB Output is correct
52 Correct 106 ms 105592 KB Output is correct
53 Correct 102 ms 105592 KB Output is correct
54 Correct 112 ms 105464 KB Output is correct
55 Correct 116 ms 105464 KB Output is correct
56 Correct 108 ms 105464 KB Output is correct
57 Correct 460 ms 166372 KB Output is correct
58 Correct 465 ms 166296 KB Output is correct
59 Correct 473 ms 166516 KB Output is correct
60 Correct 726 ms 166112 KB Output is correct
61 Correct 731 ms 166112 KB Output is correct
62 Correct 713 ms 166120 KB Output is correct
63 Correct 544 ms 151376 KB Output is correct
64 Correct 535 ms 151752 KB Output is correct
65 Correct 503 ms 151168 KB Output is correct
66 Correct 370 ms 148704 KB Output is correct
67 Correct 587 ms 165984 KB Output is correct
68 Correct 519 ms 165988 KB Output is correct
69 Correct 560 ms 165988 KB Output is correct
70 Correct 607 ms 166056 KB Output is correct
71 Correct 583 ms 165988 KB Output is correct
72 Correct 593 ms 165988 KB Output is correct
73 Correct 582 ms 165988 KB Output is correct
74 Correct 526 ms 165860 KB Output is correct
75 Correct 1504 ms 341704 KB Output is correct
76 Correct 1428 ms 341584 KB Output is correct
77 Correct 1517 ms 340688 KB Output is correct
78 Correct 1532 ms 341332 KB Output is correct
79 Correct 1466 ms 340164 KB Output is correct
80 Correct 1432 ms 340936 KB Output is correct
81 Correct 2343 ms 340172 KB Output is correct
82 Correct 2370 ms 339600 KB Output is correct
83 Correct 2353 ms 339672 KB Output is correct
84 Correct 2714 ms 339796 KB Output is correct
85 Correct 2517 ms 339660 KB Output is correct
86 Correct 2402 ms 340044 KB Output is correct
87 Execution timed out 3006 ms 339780 KB Time limit exceeded
88 Halted 0 ms 0 KB -