bzoj 2244: [SDOI2011]拦截导弹-白红宇

bzoj 2244: [SDOI2011]拦截导弹

阅读量：7159 次

发布时间：2019-06-29

本文共 2460 字，大约阅读时间需要 8 分钟。

1 #include
     
        2 #include
      
         3 #include
       
          4 #define M 100009  5 using namespace std;  6 struct data   7 {  8     int x,y,z,f[2];  9     double sum[2]; 10 }a[M],b[M]; 11 struct ss 12 { 13     int w; 14     double su; 15 }shu[M]; 16 int n,yy[M],zz[M],yl,zl,ans,tot,sta[M]; 17 double sum1; 18 bool cmp(data a1,data a2) 19 { 20     if(a1.y==a2.y) 21       return a1.x
        
         a2.x; 27 } 28 void updata(int i,int p) 29 { 30     int a1=a[i].z; 31     for(;a1<=zl;a1+=a1&-a1) 32       if(shu[a1].w
         
          >1; 65     int l1=l,l2=mid+1; 66     for(int i=l;i<=r;i++) 67       if(a[i].x<=mid) 68         b[l1++]=a[i]; 69       else 70         b[l2++]=a[i]; 71     for(int i=l;i<=r;i++) 72       a[i]=b[i]; 73     solve(l,mid,p); 74     sort(a+l,a+mid+1,cmp); 75     int st=l; 76     for(int i=mid+1;i<=r;i++) 77       { 78         for(;a[st].y<=a[i].y&&st<=mid;st++) 79           updata(st,p); 80         ask(i,p); 81       } 82     for(int i=1;i<=tot;i++) 83       shu[sta[i]].w=shu[sta[i]].su=0; 84     tot=0; 85     solve(mid+1,r,p); 86 } 87 int main() 88 { 89     scanf("%d",&n); 90     for(int i=1;i<=n;i++) 91       { 92         a[i].x=i; 93         scanf("%d%d",&a[i].y,&a[i].z); 94         yy[i]=a[i].y; 95         zz[i]=a[i].z; 96       } 97     sort(yy+1,yy+n+1); 98     sort(zz+1,zz+n+1); 99     yl=unique(yy+1,yy+n+1)-yy-1;100     zl=unique(zz+1,zz+n+1)-zz-1;101     for(int i=1;i<=n;i++)102       {103         a[i].y=yl-(lower_bound(yy+1,yy+yl+1,a[i].y)-yy)+1;104         a[i].z=zl-(lower_bound(zz+1,zz+zl+1,a[i].z)-zz)+1;105       }106     sort(a+1,a+n+1,cmp);107     solve(1,n,0);108     for(int i=1;i<=n;i++)109       {110         a[i].x=n-a[i].x+1;111         a[i].y=yl-a[i].y+1;112         a[i].z=zl-a[i].z+1;113       }114     sort(a+1,a+n+1,cmp);115     solve(1,n,1);116     sort(a+1,a+n+1,cmp1);117     for(int i=1;i<=n;i++)118       if(a[i].f[0]>ans)119         {120             ans=a[i].f[0];121             sum1=a[i].sum[0];122         }123       else if(a[i].f[0]==ans)124              sum1+=a[i].sum[0];125     printf("%d\n",ans);126     for(int i=1;i<=n;i++)127       if(a[i].f[0]+a[i].f[1]-1==ans)128         printf("%.5lf ",a[i].sum[1]*a[i].sum[0]/sum1);129       else130         printf("0.00000 ");131     return 0;132 }