Submission #1239082

#TimeUsernameProblemLanguageResultExecution timeMemory
1239082MasterDebaterDivide and conquer (IZhO14_divide)C++20
100 / 100
275 ms156208 KiB
#include<bits/stdc++.h>
using namespace std;
#define np nullptr
#define ll long long
const ll N=1e5+10,off=(1LL<<47);
ll n,ans,sumg,sumd,x[N],g[N],d[N];
struct cvor{
	ll val;
	cvor *l,*r;
	cvor(){
		val=0,l=r=np;
	}
	cvor(cvor *p){
		if(p==np)val=0,l=r=np;
		else{
			val=p->val;
			l=p->l;
			r=p->r;
		}
	}
};
cvor *tour;
ll getval(cvor *node){
	if(node==np)return 0;
	return node->val;
}
cvor *update(ll x,ll y,ll l,ll r,ll v,cvor *node){
	if(r<x or l>y)return node;
	cvor *pnovi=new cvor(node);
	if(x<=l and r<=y){
		pnovi->val=max(pnovi->val,v);
		return pnovi;
	}
	pnovi->l=update(x,y,l,(l+r)/2,v,pnovi->l);
	pnovi->r=update(x,y,(l+r)/2+1,r,v,pnovi->r);
	pnovi->val=max(getval(pnovi->l),getval(pnovi->r));
	//cout<<"u: "<<l<<' '<<r<<' '<<getval(pnovi)<<'\n';
	return pnovi;
}
ll query(ll x,ll y,ll l,ll r,cvor *node){
	if(r<x or l>y or node==np)return 0;
	//cout<<"q: "<<l<<' '<<r<<'\n';
	if(x<=l and r<=y)return node->val;
	return max(query(x,y,l,(l+r)/2,node->l),query(x,y,(l+r)/2+1,r,node->r));
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//cout<<off<<'\n';
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>x[i]>>g[i]>>d[i];
		sumd+=d[i],sumg+=g[i];
		//cout<<"update: "<<sumd-x[i]<<' '<<sumg<<'\n';
		tour=update(sumd-x[i]+off,sumd-x[i]+off,0,2*off,sumg,tour);
	}
	sumd=sumg=0;
	for(int i=0;i<n;i++){
		//cout<<"query: "<<sumd-x[i]<<' '<<2*off-1<<" | "<<query(sumd-x[i]+off,2*off-1,0,2*off,tour)<<' '<<-sumg<<'\n';
		ans=max(ans,query(sumd-x[i]+off,2*off-1,0,2*off,tour)-sumg);
		sumd+=d[i],sumg+=g[i];
		//tour=update(sumd-x[i]+off,sumd-x[i]+off,0,2*off,0,tour);
	}
	cout<<ans;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...