首页 > 代码库 > Bzoj2850 巧克力王国
Bzoj2850 巧克力王国
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
1 2 5
3 1 4
2 2 1
2 1 6
1 3 5
1 3 7
Sample Output
5
0
4
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 巧克力王国
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。