rt,本地编译能过,交到洛谷上 CE。
code:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define endl '\n'//交互题删掉
#define FastIO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define FileIO(Name) freopen(Name ".in","r",stdin);\
freopen(Name ".out","w",stdout)
#define Fix(Dec) cout<<fixed<<setprecision(Dec)
#define sp_el(i,n) " \n"[i==n]
#define put_ret(Msg) return cout<<Msg<<endl,void()
#define nonEmp(x) !x.empty()
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define VI vector<int>
#define VL vector<ll>
#ifdef DEBUG
#define msg(Msg) cerr<<Msg<<endl
#define debug(Var) cerr<<#Var<<"="<<Var<<endl
#else
#define msg(Msg)
#define debug(Var)
#endif
void Init()
{
FastIO;
}
const int N=100005;
int n,q;
struct juice
{
ll d,p,l;
bool operator<(const juice B)const
{
return d>B.d;
}
}a[N];
ll g[N],l[N],ans[N];
struct SegmentTree
{
struct node
{
ll suml,sump;
}tr[N<<2];
#define lid (id<<1)
#define rid (lid+1)
#define mid (l+r>>1)
#define rmd (mid+1)
void init(int l=1,int r=n,int id=1)
{
tr[id].suml=tr[id].sump=0;
if(l==r)return;
init(l,mid,lid);
init(rmd,r,rid);
}
void pushup(int id)
{
tr[id].suml=tr[lid].suml+tr[rid].suml;
tr[id].sump=tr[lid].sump+tr[rid].sump;
}
void modify(int lit,int pri,int l=1,int r=n,int id=1)
{
if(l==r)
{
tr[id].suml=lit;
tr[id].sump=1ll*lit*pri;
return;
}
if(pri<=mid)modify(lit,pri,l,mid,lid);
else modify(lit,pri,rmd,r,rid);
pushup(id);
}
ll query(ll need,int l=1,int r=n,int id=1)
{//If we need @need litres of juice, what's the minimum price?
if(l==r)return need*l;
if(need<=tr[lid].suml)return query(need,l,mid,lid);
if(need<=tr[id].suml)
return tr[lid].sump+query(need-tr[lid].suml,rmd,r,rid);
return LLONG_MAX;
}
#undef lid
#undef rid
#undef mid
#undef rmd
}sgt;
int nc;
struct data
{
int L,R;
VI qs;
data(int l,int r,VI &qs):L(l),R(r),qs(qs){}
};
void binary_search()
{
VI tmpq;
for(int i=1;i<=q;i++)tmpq.PB(i);
queue<data>qq;
qq.push(data(1,n,tmpq));
while(nonEmp(qq))
{
int L=qq.front().L,R=qq.front().R;
VI qs=qq.front().qs,ql,qr;
qq.pop();
if(L>R)
{
for(int i:qs)ans[i]=a[L].d;
continue;
}
int mid=L+R>>1;
if(nc>mid)sgt.init(),nc=0;
while(nc<mid)++nc,sgt.modify(a[nc].l,a[nc].p);
for(int i:qs)
if(sgt.query(l[i])<=g[i])ql.PB(i);else qr.PB(i);
qq.push(data(L,mid-1,ql));
qq.push(data(mid+1,R,qr));
}
}
void Solve()
{
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i].d>>a[i].p>>a[i].l;
sort(a+1,a+n+1);
a[n+1].d=-1;
for(int i=1;i<=q;i++)cin>>g[i]>>l[i];
/*Stop learning useless algorithms, go and solve some problems,
learn how to use*/binary_search();
for(int i=1;i<=q;i++)cout<<ans[i]<<endl;
}
void QingKong()
{
}
int main()
{
#ifdef LOCAL
ll STE=clock();
#endif
Init();
int T=1;
//cin>>T;
while(T--)
{
Solve();
QingKong();//多测不清空,抱灵两行泪
}
#ifdef LOCAL
ll ETE=clock();
cerr<<"\n\n-----------------------\nProgram done in "<<ETE-STE<<" ms";
#endif
return 0;
}