@[mmdxmqwq](/user/930076) `rgt=juice[n].d`改成了`rgt=n`，还是过不去
by mmdxmakioi @ 2023-03-24 14:14:06
过了，留个代码警示后人
```cpp
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
int n,m;
struct node
{
int d,p,l;
bool operator < (const node &aaa)const
{
return d<aaa.d;
}
}juice[200001];
int cnt;
int mx;
int T[200000];
struct node2
{
int l,r,v,p;
}Tree[8000001];
int build(int l,int r)
{
int rt=++cnt;
if(l==r)
return rt;
int mid =(l+r)/2;
Tree[rt].l=build(l,mid);
Tree[rt].r=build(mid+1,r);
return rt;
}
int update(int pre,int l,int r,int price,int size)
{
int rt=++cnt;
Tree[rt].l=Tree[pre].l;
Tree[rt].r=Tree[pre].r;
Tree[rt].p=Tree[pre].p+price*size;
Tree[rt].v=Tree[pre].v+size;
if(l==r)
{
return rt;
}
int mid=(l+r)/2;
if(mid>=price)
{
Tree[rt].l=update(Tree[pre].l,l,mid,price,size);
}
else
{
Tree[rt].r=update(Tree[pre].r,mid+1,r,price,size);
}
// Tree[rt].p=Tree[Tree[rt].l].p+Tree[Tree[rt].r].p;
// Tree[rt].v=Tree[Tree[rt].l].v+Tree[Tree[rt].r].v;
return rt;
}
int query(int u,int v,int l,int r,int sy)
{
if(l==r)
{
return sy*l;
}
int mid=(l+r)/2;
int tot=Tree[Tree[v].l].v-Tree[Tree[u].l].v;
if(sy<=tot)
{
return query(Tree[u].l,Tree[v].l,l,mid,sy);
}
else
{
return Tree[Tree[v].l].p-Tree[Tree[u].l].p+query(Tree[u].r,Tree[v].r,mid+1,r,sy-tot);
}
}
signed main()
{
int i,j;
scanf("%lld%lld",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%lld%lld%lld",&juice[i].d,&juice[i].p,&juice[i].l);
mx=max(mx,juice[i].p);
}
sort(juice+1,juice+1+n);
T[0]=build(1,mx);
for(i=1;i<=n;i++)
{
T[i]=update(T[i-1],1,mx,juice[i].p,juice[i].l);
}
// for(i=1;i<=n;i++)
// {
// printf("%lld ",Tree[T[i]].v);
// }
// printf("\n");
for(i=1;i<=m;i++)
{
int g,l;
scanf("%lld%lld",&g,&l);
int lft,rgt,ans=-1;
lft=1;
rgt=n;
while(lft<=rgt)
{
int mid=(lft+rgt)/2;
int q=query(T[mid-1],T[n],1,mx,l);
int e=Tree[T[n]].v-Tree[T[mid-1]].v;
// printf("%lld %lld %lld %lld %lld %lld %lld\n",q,e,mid,Tree[T[n]].v,Tree[T[mid-1]].v,lft,rgt);
if(query(T[mid-1],T[n],1,mx,l)<=g&&Tree[T[n]].v-Tree[T[mid-1]].v>=l)
{
lft=mid+1;
ans=mid;
}
else
{
rgt=mid-1;
}
}
if(ans==-1)
printf("%lld\n",-1ll);
else
printf("%lld\n",juice[ans].d);
}
}
```
by mmdxmakioi @ 2023-03-24 14:31:31