题目链接：
显然如果美味度高的合法那么美味度低的一定合法，因为美味度低的可选方案包含美味度高的可选方案。
那么我们二分一个美味度作为答案然后考虑如何验证？
选择时显然要贪心的先选单价低的果汁。
那么我们按美味度从大到小将每种果汁排序，然后对于每种果汁建立一个版本的主席树，主席树维护的权值是果汁单价。
每次验证时在对应版本主席树中查找，如果左子树中总体积大于L则递归左子树，否则将答案加上左子树所有果汁的总价然后递归右子树。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
struct miku
{
int d;
ll g,l;
}s[100010];
int cnt;
int n,m,q;
ll G,L;
int ls[2000010];
int rs[2000010];
ll sum[2000010];
ll num[2000010];
int root[100010];
ll h[100010];
bool cmp(miku a,miku b)
{
if(a.d!=b.d)
{
return a.d>b.d;
}
return a.g<b.g;
}
void updata(int &rt,int pre,int l,int r,int x,ll val,ll lim)
{
rt=++cnt;
sum[rt]=sum[pre]+val;
num[rt]=num[pre]+lim;
ls[rt]=ls[pre];
rs[rt]=rs[pre];
if(l==r)
{
return ;
}
int mid=(l+r)>>1;
if(x<=mid)
{
updata(ls[rt],ls[pre],l,mid,x,val,lim);
}
else
{
updata(rs[rt],rs[pre],mid+1,r,x,val,lim);
}
}
ll query(int rt,int l,int r,ll k)
{
if(l==r)
{
return k*h[l];
}
int mid=(l+r)>>1;
if(num[ls[rt]]>=k)
{
return query(ls[rt],l,mid,k);
}
else
{
return sum[ls[rt]]+query(rs[rt],mid+1,r,k-num[ls[rt]]);
}
}
bool check(int x)
{
if(num[root[x]]<L)
{
return false;
}
if(query(root[x],1,m,L)<=G)
{
return true;
}
return false;
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d%lld%lld",&s[i].d,&s[i].g,&s[i].l);
h[i]=s[i].g;
}
sort(s+1,s+1+n,cmp);
sort(h+1,h+1+n);
m=unique(h+1,h+1+n)-h-1;
for(int i=1;i<=n;i++)
{
updata(root[i],root[i-1],1,m,lower_bound(h+1,h+1+m,s[i].g)-h,s[i].g*s[i].l,s[i].l);
}
while(q--)
{
scanf("%lld%lld",&G,&L);
int l=1;
int r=n;
int ans=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)==true)
{
ans=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
if(ans==-1)
{
printf("-1\n");
continue;
}
printf("%d\n",s[ans].d);
}
}