首页 > 代码库 > Bzoj2850 巧克力王国

Bzoj2850 巧克力王国

2024-08-30 00:08:19   220人阅读

Time Limit: 60 Sec  Memory Limit: 512 MB
Submit: 505  Solved: 204

Description

巧克力王国里的巧克力都是由牛奶和可可做成的。但是并不是每一块巧克力都受王国人民的欢迎，因为大家都不喜
欢过于甜的巧克力。对于每一块巧克力，我们设x和y为其牛奶和可可的含量。由于每个人对于甜的程度都有自己的
评判标准，所以每个人都有两个参数a和b，分别为他自己为牛奶和可可定义的权重，因此牛奶和可可含量分别为x
和y的巧克力对于他的甜味程度即为ax + by。而每个人又有一个甜味限度c，所有甜味程度大于等于c的巧克力他都
无法接受。每块巧克力都有一个美味值h。现在我们想知道对于每个人，他所能接受的巧克力的美味值之和为多少

Input

第一行两个正整数n和m，分别表示巧克力个数和询问个数。接下来n行，每行三个整数x,y,h，含义如题目所示。再
接下来m行，每行三个整数a,b,c，含义如题目所示。

 

Output

输出m行，其中第i行表示第i个人所能接受的巧克力的美味值之和。

 

Sample Input

3 3
1 2 5
3 1 4
2 2 1
2 1 6
1 3 5
1 3 7

Sample Output

5
0
4

HINT

 

1 <= n, m <= 50000，1 <= 10^9，-10^9 <= a, b, x, y <= 10^9。

Source

Violet 0

 

K-D tree

以x和y为坐标，通过ax+by估价来优化查询

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<queue> 6 using namespace std; 7 const int mxn=100010; 8 int read(){ 9     int x=0,f=1;char ch=getchar();10     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}11     while(ch>=‘0‘ && ch<=‘9‘){x=x*10-‘0‘+ch;ch=getchar();}12     return x*f;13 }14 struct node{15     int max[2],min[2];16     int l,r;17     int d[2],v;18     long long sum;19 }t[mxn];20 int nowD=0;21 int cmp(const node a,const node b){22     return (a.d[nowD]<b.d[nowD] || (a.d[nowD]==b.d[nowD] && a.d[nowD^1]<b.d[nowD^1]));23 }24 int root,nct=0;25 int n,m;26 long long a,b,c,ans=0; 27 void pushup(int rt,int x){28     t[rt].max[0]=max(t[rt].max[0],t[x].max[0]);29     t[rt].max[1]=max(t[rt].max[1],t[x].max[1]);30     t[rt].min[0]=min(t[rt].min[0],t[x].min[0]);31     t[rt].min[1]=min(t[rt].min[1],t[x].min[1]);32     return; 33 }34 int Build(int l,int r,int D){35     nowD=D;36     int mid=(l+r)>>1;37     nth_element(t+l,t+mid,t+r+1,cmp);38     t[mid].max[0]=t[mid].min[0]=t[mid].d[0];39     t[mid].max[1]=t[mid].min[1]=t[mid].d[1];40     if(l!=mid){t[mid].l=Build(l,mid-1,D^1);pushup(mid,t[mid].l);}41     if(r!=mid){t[mid].r=Build(mid+1,r,D^1);pushup(mid,t[mid].r);}42     t[mid].sum=t[t[mid].l].sum+t[t[mid].r].sum+t[mid].v;43     return mid;44 }45 inline bool pd(long long x,long long y){return (a*x+b*y<c);}46 int cnt(int rt){47     int res=0;48     if(pd(t[rt].max[0],t[rt].max[1]))res++;49     if(pd(t[rt].min[0],t[rt].max[1]))res++;50     if(pd(t[rt].max[0],t[rt].min[1]))res++;51     if(pd(t[rt].min[0],t[rt].min[1]))res++;52     return res;53 }54 void query(int rt){55     if(pd(t[rt].d[0],t[rt].d[1]))ans+=t[rt].v;56     int L=0,R=0;57     if(t[rt].l)L=cnt(t[rt].l);58     if(t[rt].r)R=cnt(t[rt].r);59     if(L==4){ans+=t[t[rt].l].sum;}//还要算R所以不能return 60         else if(L)query(t[rt].l);61     if(R==4){ans+=t[t[rt].r].sum;} 62         else if(R)query(t[rt].r);63     return;64 }65 int main(){66     n=read();m=read();67     int i,j;68     for(i=1;i<=n;i++){69         t[i].d[0]=read();t[i].d[1]=read();t[i].v=read();70     }71     root=Build(1,n,0);72     for(i=1;i<=m;i++){73         a=read();b=read();c=read();74         ans=0;75         query(root);76         printf("%lld\n",ans);77     }78     return 0;79 }

 

Bzoj2850 巧克力王国


联系
我们