BZOJ 3276:磁力

#include<cstdio>

#include<algorithm>

#define N 250010

typedef long long ll;

int n,i,x0,y0,nowp,x,y,r,c,v[N<<2],tmp,h=1,t,q[N];ll nowr;

struct P{int m,p;ll d,r;}a[N];

inline bool cmp(P x,P y){return x.d<y.d;}

inline void read(int&a){

  char c;bool f=0;a=0;

  while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));

  if(c!='-')a=c-'0';else f=1;

  while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';

  if(f)a=-a;

}

inline ll sqr(ll x){return x*x;}

inline int lower(){

  int l=1,r=n,t=0,mid;

  while(l<=r)if(a[mid=(l+r)>>1].d<=nowr)l=(t=mid)+1;else r=mid-1;

  return t;

}

inline int merge(int x,int y){

  if(!x)return y;

  if(!y)return x;

  return a[x].m<a[y].m?x:y;

}

inline void up(int x){v[x]=merge(v[x<<1],v[x<<1|1]);}

void build(int x,int a,int b){

  if(a==b){v[x]=a;return;}

  int mid=(a+b)>>1;

  build(x<<1,a,mid),build(x<<1|1,mid+1,b),up(x);

}

void change(int x,int a,int b,int c){

  if(a==b){v[x]=0;return;}

  int mid=(a+b)>>1;

  c<=mid?change(x<<1,a,mid,c):change(x<<1|1,mid+1,b,c);

  up(x);

}

void ask(int x,int a,int b){

  if(b<=c){tmp=merge(tmp,v[x]);return;}

  int mid=(a+b)>>1;

  ask(x<<1,a,mid);

  if(c>mid)ask(x<<1|1,mid+1,b);

}

int main(){

  read(x0),read(y0),read(nowp),read(r),read(n),nowr=sqr(r);

  for(i=1;i<=n;i++){

    read(x),read(y),read(a[i].m),read(a[i].p),read(r);

    a[i].d=sqr(x-x0)+sqr(y-y0),a[i].r=sqr(r);

  }

  std::sort(a+1,a+n+1,cmp),build(1,1,n);

  if(c=lower())while(1){

    tmp=0,ask(1,1,n);

    if(!tmp||a[tmp].m>nowp)break;

    change(1,1,n,q[++t]=tmp);

  }

  while(h<=t){

    nowp=a[q[h]].p,nowr=a[q[h++]].r;

    if(c=lower())while(1){

      tmp=0,ask(1,1,n);

      if(!tmp||a[tmp].m>nowp)break;

      change(1,1,n,q[++t]=tmp);

    }

  }

  return printf("%d",t),0;

}