【HDU】3255 Farming

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 typedef __int64 LL;
  5 #define MAXN 30010
  6 using namespace std;
  7 struct Plant
  8 {
  9     int x1,y1,x2,y2,s;
 10 };
 11 struct Seg
 12 {
 13     int left,right,high,flag;
 14     friend bool operator<(Seg a,Seg b)
 15     {
 16         if(a.high==b.high)
 17             return a.flag<b.flag;
 18         return a.high<b.high;
 19     }
 20 };
 21 struct node
 22 {
 23     int val,cover;
 24 }tree[MAXN<<3];
 25 Seg s[MAXN<<1];
 26 Plant p[MAXN];
 27 int price[4],X[MAXN<<1];
 28 inline void PushUp(int L,int R,int rt)
 29 {
 30     if(tree[rt].cover)
 31         tree[rt].val=X[R+1]-X[L];
 32     else
 33     {
 34         if(L==R)
 35             tree[rt].val=0;
 36         else
 37             tree[rt].val=tree[rt<<1].val+tree[rt<<1|1].val;
 38     }
 39 }
 40 void Update(int x,int y,int flag,int L,int R,int rt)
 41 {
 42     if(x<=L&&R<=y)
 43     {
 44         tree[rt].cover+=flag;
 45         PushUp(L,R,rt);
 46     }
 47     else
 48     {
 49         int mid=(L+R)>>1;
 50         if(x<=mid)
 51             Update(x,y,flag,L,mid,rt<<1);
 52         if(y>mid)
 53             Update(x,y,flag,mid+1,R,rt<<1|1);
 54         PushUp(L,R,rt);
 55     }
 56 }
 57 int main()
 58 {
 59     LL temp,ans;
 60     int t,n,m,i,j,cnt,nx,x,y,ca=1;
 61     scanf("%d",&t);
 62     while(t--)
 63     {
 64         scanf("%d%d",&n,&m);
 65         m++;
 66         price[0]=0;
 67         for(i=1;i<m;i++)
 68             scanf("%d",&price[i]);
 69         for(i=nx=0;i<n;i++)
 70         {
 71             scanf("%d%d%d%d%d",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2,&p[i].s);
 72             p[i].s=price[p[i].s];
 73             X[nx++]=p[i].x1;
 74             X[nx++]=p[i].x2;
 75         }
 76         sort(price,price+m);
 77         sort(X,X+nx);
 78         nx=unique(X,X+nx)-X;
 79         ans=0;
 80         memset(tree,0,sizeof(tree));
 81         for(i=1;i<m;i++)
 82         {
 83             for(j=cnt=0;j<n;j++)
 84             {
 85                 if(p[j].s>=price[i])
 86                 {
 87                     s[cnt].left=p[j].x1;
 88                     s[cnt].right=p[j].x2;
 89                     s[cnt].high=p[j].y1;
 90                     s[cnt++].flag=1;
 91                     s[cnt].left=p[j].x1;
 92                     s[cnt].right=p[j].x2;
 93                     s[cnt].high=p[j].y2;
 94                     s[cnt++].flag=-1;
 95                 }
 96             }
 97             sort(s,s+cnt);
 98             for(temp=j=0;j<cnt;j++)
 99             {
100                 x=lower_bound(X,X+nx,s[j].left)-X;
101                 y=lower_bound(X,X+nx,s[j].right)-X;
102                 Update(x,y-1,s[j].flag,0,nx-2,1);
103                 if(j+1<cnt)
104                     temp+=(LL)(s[j+1].high-s[j].high)*tree[1].val;
105             }
106             ans+=temp*(price[i]-price[i-1]);
107         }
108         printf("Case %d: %I64d\n",ca++,ans);
109     }
110     return 0;
111 }
新博客：www.zhixiangli.com