[CTSC2018]混合果汁

主席树 二分

题面

戳我

解析

热烈庆祝中国最难OI赛事CTSC au线达到NOI水平
显然，我们可以二分出美味值的下界。
然后发现各个价格的果汁好像并没有什么区别。
那么贪心尽可能取其小者就好。
求前$k$小？
主席树轻松解决。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define ls x<<1
#define rs x<<1|1
#define max(a,b) (a>b?a:b)
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e5+100;
ll n,m,tot,mxd,mxp,p,v,rt[N*100];
struct fru
{
  ll d,p,v;
  bool operator < (const fru &o) const {return d<o.d;}
}a[N];
struct chi
{
  ll p,v;
}b[N];
struct tree
{
  ll l,r,sum,num;
}t[N*100];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void Modify(re ll &x,re ll y,re ll l,re ll r,re ll p,re ll v)
{
  t[x=++tot]=t[y];
  t[x].num+=v;
  t[x].sum+=v*p;
  re ll mid=l+r>>1;
  if(l==r) return;
  if(p<=mid) Modify(t[x].l,t[y].l,l,mid,p,v);
  else Modify(t[x].r,t[y].r,mid+1,r,p,v);
}
il int Query(re ll x,re ll y,re ll l,re ll r,re ll p,re ll v)
{
  re ll num=t[t[x].l].num-t[t[y].l].num,sum=t[t[x].l].sum-t[t[y].l].sum;
  if(l==r)
    {
      re ll l1=t[x].num-t[y].num,l2=t[x].sum-t[y].sum;
      if(l1<v) return 0;
      return p>=(l2/l1)*v;
    }
  re ll mid=l+r>>1;
  if(num>=v)
    {
      if(p>=sum) return 1;
      return Query(t[x].l,t[y].l,l,mid,p,v);
    }
  else
    {
      if(p<sum) return 0;
      return Query(t[x].r,t[y].r,mid+1,r,p-sum,v-num);
    }
} 
il bool check(re ll x)
{
  re ll l=1,r=n;
  while(l<r)
    {
      re ll mid=l+r>>1;
      if(a[mid].d>=x) r=mid;
      else l=mid+1;
    }
  return Query(rt[n],rt[l-1],1,mxp,p,v);
}
il ll solve()
{
  re ll l=1,r=mxd;
  if(!check(1)) return -1;
  while(l<r)
    {
      re ll mid=l+r+1>>1;
      if(check(mid)) l=mid;
      else r=mid-1;
    }
  return l;//我们取的是最小值，所以要用l
}
int main()
{
  n=gi();m=gi();
  fp(i,1,n) a[i].d=gi(),a[i].p=gi(),a[i].v=gi(),mxd=max(mxd,a[i].d),mxp=max(mxp,a[i].p);
  sort(a+1,a+1+n);
  fp(i,1,n) Modify(rt[i],rt[i-1],1,mxp,a[i].p,a[i].v);
  fp(i,1,m)
    {
      p=gi(),v=gi();
      printf("%lld\n",solve());
    }
  return 0;
}