oj.uz

Submission #272356

# Submission time Handle Problem Language Result Execution time Memory
272356 2020-08-18T11:31:43 Z MKopchev Circle selection (APIO18_circle_selection) C++14
0 / 100
 3000 ms 252580 KB 
#include<bits/stdc++.h>
using namespace std;
const int nmax=3e5+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];

set< pair<int/*y*/,int/*id*/> > tree[nmax*4];

void update(int node,int l,int r,int pos,circle cur)
{
    //cout<<node<<" -> "<<cur.y<<" "<<cur.id<<endl;

    tree[node].insert({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 match(int node,int l,int r,int lq,int rq,circle cur)
{
    if(l==lq&&r==rq)
    {
        int y1=cur.y-2*cur.r;
        int y2=cur.y+2*cur.r;

        set< pair<int/*y*/,int/*id*/> >::iterator it=tree[node].lower_bound({y1,0});

        vector< pair<int/*y*/,int/*id*/> > to_pop={};

        while(it!=tree[node].end())
        {
            pair<int/*y*/,int/*id*/> info=*it;

            if(info.first>y2)break;

            if(outp[info.second]==0)
            {
                if(touch(inp[info.second],cur))
                {
                    //cout<<"touch "<<info.second<<" "<<cur.id<<" "<<endl;

                    outp[info.second]=cur.id;
                }
            }

            if(outp[info.second])to_pop.push_back(info);

            it++;
        }

        for(auto k:to_pop)
            tree[node].erase(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=sorted_inp[which].x-2*sorted_inp[which].r;
    int x2=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--;

    if(le>ri)return;

    match(1,1,n,le,ri,sorted_inp[which]);
}
int 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<=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 main()':
circle_selection.cpp:137:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  137 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |     ^~~
circle_selection.cpp:137:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  137 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |                                                ^~~~~~
circle_selection.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
circle_selection.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  114 |         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 38 ms 56728 KB Output is correct
2 Correct 45 ms 56760 KB Output is correct
3 Correct 44 ms 56744 KB Output is correct
4 Correct 36 ms 56692 KB Output is correct
5 Correct 70 ms 56696 KB Output is correct
6 Incorrect 39 ms 56704 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 240460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 56704 KB Output is correct
2 Correct 1696 ms 147164 KB Output is correct
3 Execution timed out 3094 ms 229628 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3087 ms 252580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 56728 KB Output is correct
2 Correct 45 ms 56760 KB Output is correct
3 Correct 44 ms 56744 KB Output is correct
4 Correct 36 ms 56692 KB Output is correct
5 Correct 70 ms 56696 KB Output is correct
6 Incorrect 39 ms 56704 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 56728 KB Output is correct
2 Correct 45 ms 56760 KB Output is correct
3 Correct 44 ms 56744 KB Output is correct
4 Correct 36 ms 56692 KB Output is correct
5 Correct 70 ms 56696 KB Output is correct
6 Incorrect 39 ms 56704 KB Output isn't correct
7 Halted 0 ms 0 KB -