oj.uz

Submission #272669

# Submission time Handle Problem Language Result Execution time Memory
272669 2020-08-18T13:17:57 Z MKopchev Circle selection (APIO18_circle_selection) C++14
0 / 100
 2135 ms 770132 KB 
#include<bits/stdc++.h>
using namespace std;
const int nmax=3e5+42,inf=1e9+42;

struct circle
{
    int x,y,r,id;
};

int n;
circle inp[nmax],sorted_inp[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;
}

int outp[nmax];

vector< pair<int/*y*/,int/*id*/> > nodes[nmax*4];
vector<int> prv[nmax*4];
vector<int> nxt[nmax*4];
vector<int> tree[nmax*4];

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);
}
void build(int where,int node,int l,int r)
{
    while(tree[where].size()<=node)tree[where].push_back(0);
    tree[where][node]=r-l+1;

    if(l==r)return;

    int av=(l+r)/2;

    build(where,node*2,l,av);
    build(where,node*2+1,av+1,r);
}
void sub_tree(int where,int node,int l,int r,int pos)
{
    tree[where][node]--;

    if(l==r)return;

    int av=(l+r)/2;

    if(pos<=av)sub_tree(where,node*2,l,av,pos);
    else sub_tree(where,node*2+1,av+1,r,pos);
}
int query(int where,int node,int l,int r,int lq,int rq)
{
    if(tree[where][node]==0)return -1;

    if(l==r)return l;

    int av=(l+r)/2;

    if(lq<=av)
    {
        int mem=query(where,node*2,l,av,lq,min(av,rq));
        if(mem!=-1)return mem;
    }
    if(av<rq)
    {
        int mem=query(where,node*2+1,av+1,r,max(av+1,lq),rq);
        if(mem!=-1)return mem;
    }
    return -1;
}
int find_first(int where,int start)
{
    return query(where,1,0,nodes[where].size()-1,start,nodes[where].size()-1);
}

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(tree[node][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,1,0,nodes[node].size()-1,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];

    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,sorted_inp[i].x)-help_x;

        update(1,1,n,pos,sorted_inp[i]);
    }

    for(int i=1;i<=4*n;i++)
        if(nodes[i].size())
        {
            sort(nodes[i].begin(),nodes[i].end());
            for(int j=0;j<nodes[i].size();j++)
            {
                prv[i].push_back(j-1);
                nxt[i].push_back(j+1);
            }
            build(i,1,0,nodes[i].size()-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 'void build(int, int, int, int)':
circle_selection.cpp:51:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |     while(tree[where].size()<=node)tree[where].push_back(0);
      |           ~~~~~~~~~~~~~~~~~~^~~~~~
circle_selection.cpp: In function 'void match(int, int, int, int, int, circle)':
circle_selection.cpp:118: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]
  118 |         if(start==nodes[node].size())return;
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:133: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]
  133 |         while(start<nodes[node].size()&&nodes[node][start].first<=y2)
      |               ~~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:155: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]
  155 |             if(nxt[node][k]<nodes[node].size())
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:219: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]
  219 |             for(int j=0;j<nodes[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~
circle_selection.cpp:231:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  231 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |     ^~~
circle_selection.cpp:231:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  231 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |                                                ^~~~~~
circle_selection.cpp:193:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  193 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
circle_selection.cpp:196:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  196 |         scanf("%i%i%i",&inp[i].x,&inp[i].y,&inp[i].r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 113016 KB Output is correct
2 Correct 78 ms 113016 KB Output is correct
3 Correct 78 ms 113016 KB Output is correct
4 Correct 77 ms 113016 KB Output is correct
5 Correct 77 ms 113016 KB Output is correct
6 Correct 79 ms 113144 KB Output is correct
7 Correct 78 ms 113272 KB Output is correct
8 Correct 78 ms 113144 KB Output is correct
9 Correct 78 ms 113144 KB Output is correct
10 Correct 77 ms 113160 KB Output is correct
11 Correct 77 ms 113144 KB Output is correct
12 Correct 78 ms 113144 KB Output is correct
13 Correct 78 ms 113144 KB Output is correct
14 Correct 77 ms 113144 KB Output is correct
15 Correct 78 ms 113188 KB Output is correct
16 Correct 84 ms 113600 KB Output is correct
17 Correct 80 ms 113528 KB Output is correct
18 Correct 80 ms 113536 KB Output is correct
19 Correct 95 ms 116728 KB Output is correct
20 Correct 94 ms 116728 KB Output is correct
21 Correct 98 ms 116728 KB Output is correct
22 Correct 99 ms 116600 KB Output is correct
23 Runtime error 237 ms 235896 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1905 ms 388816 KB Output is correct
2 Correct 1951 ms 393156 KB Output is correct
3 Correct 1918 ms 393024 KB Output is correct
4 Correct 2078 ms 392808 KB Output is correct
5 Runtime error 2108 ms 747656 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 113016 KB Output is correct
2 Runtime error 839 ms 379036 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 2135 ms 770132 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 113016 KB Output is correct
2 Correct 78 ms 113016 KB Output is correct
3 Correct 78 ms 113016 KB Output is correct
4 Correct 77 ms 113016 KB Output is correct
5 Correct 77 ms 113016 KB Output is correct
6 Correct 79 ms 113144 KB Output is correct
7 Correct 78 ms 113272 KB Output is correct
8 Correct 78 ms 113144 KB Output is correct
9 Correct 78 ms 113144 KB Output is correct
10 Correct 77 ms 113160 KB Output is correct
11 Correct 77 ms 113144 KB Output is correct
12 Correct 78 ms 113144 KB Output is correct
13 Correct 78 ms 113144 KB Output is correct
14 Correct 77 ms 113144 KB Output is correct
15 Correct 78 ms 113188 KB Output is correct
16 Correct 84 ms 113600 KB Output is correct
17 Correct 80 ms 113528 KB Output is correct
18 Correct 80 ms 113536 KB Output is correct
19 Correct 95 ms 116728 KB Output is correct
20 Correct 94 ms 116728 KB Output is correct
21 Correct 98 ms 116728 KB Output is correct
22 Correct 99 ms 116600 KB Output is correct
23 Runtime error 237 ms 235896 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 113016 KB Output is correct
2 Correct 78 ms 113016 KB Output is correct
3 Correct 78 ms 113016 KB Output is correct
4 Correct 77 ms 113016 KB Output is correct
5 Correct 77 ms 113016 KB Output is correct
6 Correct 79 ms 113144 KB Output is correct
7 Correct 78 ms 113272 KB Output is correct
8 Correct 78 ms 113144 KB Output is correct
9 Correct 78 ms 113144 KB Output is correct
10 Correct 77 ms 113160 KB Output is correct
11 Correct 77 ms 113144 KB Output is correct
12 Correct 78 ms 113144 KB Output is correct
13 Correct 78 ms 113144 KB Output is correct
14 Correct 77 ms 113144 KB Output is correct
15 Correct 78 ms 113188 KB Output is correct
16 Correct 84 ms 113600 KB Output is correct
17 Correct 80 ms 113528 KB Output is correct
18 Correct 80 ms 113536 KB Output is correct
19 Correct 95 ms 116728 KB Output is correct
20 Correct 94 ms 116728 KB Output is correct
21 Correct 98 ms 116728 KB Output is correct
22 Correct 99 ms 116600 KB Output is correct
23 Runtime error 237 ms 235896 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -