CH Round #46A 磁力块

还是一道好题的

对于一个磁石是否被吸引，有两个关键字：距离和质量。（二维偏序？？）

好像是很厉害的分块姿势，先按第一关键字排序，在块中按第二关键字排

进行bfs，对于当前磁石，有1~k-1个块是第一关键字全部小于等于当前磁石的，那么暴力从块首往后，找到第一个第二关键字大于当前磁石属性的，那么前面都捡走，以后可以从这里开始找。

暴力枚举第k个块找答案。

一个优化就是找k的时候直接比较当前块的最大值就行了，因为当前的属性肯定是>kmin，<kmax滴

（垃圾CH本机AC提交WA幸好最后我搞对了）

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

int n;

struct node{LL dis,m,p,r;}a[];bool v[];

bool cmp1(node n1,node n2){return n1.m<n2.m;}

bool cmp2(node n1,node n2){return n1.dis<n2.dis;}

int block,st[];

struct LIST

{

    LL p,r;

}list[];

int be[];LL mx[];

int findk(LL p)

{

    for(int i=;i<=block;i++)

        if(p<mx[i])return i;

    return block+;

}

int main()

{

    freopen("1.in","r",stdin);

    freopen("1.out","w",stdout);

    LL xx,yy,x,y;

    scanf("%lld%lld%lld%lld%d",&xx,&yy,&list[].p,&list[].r,&n);

    for(int i=;i<=n;i++)

    {

        scanf("%lld%lld%lld%lld%lld",&x,&y,&a[i].m,&a[i].p,&a[i].r);

        a[i].dis=(x-xx)*(x-xx)+(y-yy)*(y-yy);

    }

    sort(a+,a+n+,cmp1);

    block=(int(sqrt(double(n+))))+;

    for(int i=;i<=n;i++)st[i]=(i-)/block+;

    for(int i=;i<=block;i++)

    {

        int St=(i-)*block+,Ed=min(i*block,n);mx[i]=a[Ed].m;

        if(St<=Ed)sort(a+St,a+Ed+,cmp2);

    }

    for(int i=;i<=block;i++)be[i]=;

    memset(v,false,sizeof(v));

    int head=,tail=,ans=;

    while(head<tail)

    {

        LL p=list[head].p,r=list[head].r;

        int k=findk(p);

        for(int i=;i<=k-;i++)

        {

            for(int j=be[i];j<=block&&(i-)*block+j<=n;j++)

            {

                int u=(i-)*block+j;

                if(a[u].dis>r*r){be[i]=j;break;}

                {

                    if(v[u]==false)

                    {

                        v[u]=true;

                        ans++;

                        list[tail].p=a[u].p, list[tail].r=a[u].r;

                        tail++;

                    }

                }

            }

        }

        if(k!=block+)

        {

            for(int j=be[k];j<=block&&(k-)*block+j<=n;j++)

            {

                int u=(k-)*block+j;

                if(a[u].dis>r*r)break;

                else if(a[u].m<=p)

                {

                    if(v[u]==false)

                    {

                        v[u]=true;

                        ans++;

                        list[tail].p=a[u].p, list[tail].r=a[u].r;

                        tail++;

                    }

                }

            }

        }

        head++;

    }

    printf("%d\n",ans);

    return ;

}

巴特西

CH Round #46A 磁力块

最新文章

热门文章