Submission #182426

#	Time	Username	Problem	Language	Result	Execution time	Memory
182426		mahmoudbadawy	Divide and conquer (IZhO14_divide)	C++17	100 / 100	277 ms	12532 KiB

divide

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+5;

int x[N],g[N],e[N];
long long gs[N],es[N],dp[N],btree[8*N];
int n;
vector<long long> cmp;

int get(long long x)
{
	return lower_bound(cmp.begin(),cmp.end(),x)-cmp.begin();
}

void update(int node,int l,int r,int ind,long long val)
{
	//if(ind<l||ind>r) return;
	if(l==r)
	{
		btree[node]=max(btree[node],val);
		return;
	}
	int mid=(l+r)/2;
	if(ind<=mid)
		update(node*2,l,mid,ind,val);
	else
		update(node*2+1,mid+1,r,ind,val);
	btree[node]=max(btree[node*2],btree[node*2+1]);
}

long long query(int node,int l,int r,int ql,int qr)
{
	if(r<ql||qr<l) return 0;
	if(ql<=l&&r<=qr) return btree[node];
	int mid=(l+r)/2;
	return max(query(node*2,l,mid,ql,qr),query(node*2+1,mid+1,r,ql,qr));
}

int main()
{
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> x[i] >> g[i] >> e[i];
		gs[i]=g[i]+gs[i-1];
		es[i]=e[i]+es[i-1];
		// e[j] - e[i-1] >= (x[j]-x[i])
		// e[j] - x[j] >= e[i-1]-x[i]
		cmp.push_back(es[i]-x[i]);
		cmp.push_back(es[i-1]-x[i]);
	}
	sort(cmp.begin(),cmp.end());
	cmp.erase(unique(cmp.begin(),cmp.end()),cmp.end());
	long long mx=0;
	for(int i=n;i>=1;i--)
	{
		mx=max(mx,1LL*g[i]);
		//cout << es[i-1]-x[i]+1 << " " << es[i]-x[i] << endl;
		dp[i]=max(mx,query(1,0,cmp.size()-1,get(es[i-1]-x[i]),cmp.size()-1)-gs[i-1]);
		//cout << dp[i] << endl;
		mx=max(mx,dp[i]);
		update(1,0,cmp.size()-1,get(es[i]-x[i]),gs[i]);
	}
	cout << dp[1] << endl;
}

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