Submission #1239077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239077		MasterDebater	Divide and conquer (IZhO14_divide)	C++20	0 / 100	1 ms	584 KiB

divide

#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;
int 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){
		if(v==0)pnovi->val=0;
		else pnovi->val=max(pnovi->val,v);
		//cout<<"napravljen update: "<<l<<' '<<r<<' '<<pnovi->val<<'\n';
		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));
	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;
	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);
	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]<<" inf "<<-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;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 31
• Subtask 3: 0 / 52