题目描述
小 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。
| 测试点编号 | n= | m= | 其他限制 |
|---|---|---|---|
| 1,2,3 | 10 | 10 | 无 |
| 4,5,6 | 500 | 500 | 无 |
| 7,8,9 | 5000 | 5000 | 无 |
| 10,11,12 | 100000 | 100000 | pi=1 |
| 13,14,15 | 100000 | 100000 | li=1 |
| 16,17,18,19,20 | 100000 | 100000 | 无 |
代码实现：
#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; }
