CE 求助
查看原帖
CE 求助
549499
Disjoint_cat楼主2023/8/7 21:50

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;
}
2023/8/7 21:50
加载中...