企业官网建设流程全解析

题目描述

小 R 热衷于做黑暗料理，尤其是混合果汁。

商店里有 n 种果汁，编号为 0,1,⋯,n−1 。i 号果汁的美味度是 di​，每升价格为 pi​。小 R 在制作混合果汁时，还有一些特殊的规定，即在一瓶混合果汁中，i 号果汁最多只能添加 li​ 升。

现在有 m 个小朋友过来找小 R 要混合果汁喝，他们都希望小 R 用商店里的果汁制作成一瓶混合果汁。其中，第 j 个小朋友希望他得到的混合果汁总价格不大于 gj​，体积不小于 Lj​。在上述这些限制条件下，小朋友们还希望混合果汁的美味度尽可能地高，一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小朋友能喝到的最美味的混合果汁的美味度。

输入格式

输入第一行包含两个正整数 n,m，表示果汁的种数和小朋友的数量。

接下来 n 行，每行三个正整数 di​,pi​,li​，表示 i 号果汁的美味度为 di​，每升价格为 pi​，在一瓶果汁中的添加上限为 li​。

接下来 m 行依次描述所有小朋友：每行两个数正整数 gj​,Lj​ 描述一个小朋友，表示他最多能支付 gj​ 元钱，他想要至少 Lj​ 升果汁。

输出格式

对于所有小朋友依次输出：对于每个小朋友，输出一行，包含一个整数，表示他能喝到的最美味的混合果汁的美味度。如果无法满足他的需求，则输出 −1。

输入输出样例

输入 #1复制

3 4 1 3 5 2 1 3 3 2 5 6 3 5 3 10 10 20 10

输出 #1复制

3 2 -1 1

说明/提示

对于所有的测试数据，保证 n,m≤100000，1≤di​,pi​,li​≤105，1≤gj​,Lj​≤1018。

代码实现：

#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #define N 100005 #define INF 0x3f3f3f3f using namespace std; inline int rd(){ int x=0,y=0; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();} while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return y?-x:x; } template<typename T> inline T rd(){ T x=0; int y=0; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();} while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return y?-x:x; } int rt[N]; struct drink{ int d, l, rk; long long p; }dr[N]; struct ct{ int lc[N<<5], rc[N<<5], cnt; long long s[N<<5], c[N<<5], val[N<<5]; // s: l*p的和, c: l的和, val: 叶子节点的p #define lc(x) lc[x] #define rc(x) rc[x] void build(int pos, int l, int r, int &nd, int old, long long L, long long P){ nd=++cnt; s[nd]=s[old]+L*P; c[nd]=c[old]+L; if(l==r){ val[nd]=P; return; } int mid=l+r>>1; if(pos<=mid)rc(nd)=rc(old),build(pos,l,mid,lc(nd),lc(old),L,P); else lc(nd)=lc(old),build(pos,mid+1,r,rc(nd),rc(old),L,P); } long long qry(int l, int r, int nd, long long g){ if(l==r)return nd?min((g/val[nd]),c[nd]):0; int mid=l+r>>1; if(s[lc(nd)]>g)return qry(l,mid,lc(nd),g); else return qry(mid+1,r,rc(nd),g-s[lc(nd)])+c[lc(nd)]; } }tr; inline bool cmp1(drink x, drink y){return x.p < y.p;} inline bool cmp2(drink x, drink y){return x.d > y.d;} int main(){ int n=rd(), m=rd(); for(register int i=1;i<=n;++i) dr[i].d=rd(), dr[i].p=rd<long long>(), dr[i].l=rd(); sort(dr+1, dr+1+n, cmp1); for(register int i=1;i<=n;++i)dr[i].rk=i; sort(dr+1, dr+1+n, cmp2); for(register int i=1;i<=n;++i) tr.build(dr[i].rk, 1, n, rt[i], rt[i-1], dr[i].l, dr[i].p); int l, r; while(m--){ long long g=rd<long long>(), L=rd<long long>(); int ans=-1; l=1, r=n; while(l<=r){ int mid=l+r>>1; long long k=tr.qry(1, n, rt[mid], g); if(k>=L)ans=dr[mid].d, r=mid-1; else l=mid+1; } printf("%d\n", ans); } return 0; }