Submission #86759

#	Time	Username	Problem	Language	Result	Execution time	Memory
86759		Weak123456	Divide and conquer (IZhO14_divide)	C++17	17 / 100	157 ms	9292 KiB

divide

#include<bits/stdc++.h>
#define P pair<lli, lli>
#define x first
#define y second
#define mp make_pair
using namespace std;
typedef long long int lli;
const lli N=100009, inf=1e16;
lli n, l[N], r[N], b[N], s[N], sg[N];
struct T
{
	lli x, g, e;
};
T a[N];
void Inp()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].g>>a[i].e;
		s[i]=s[i-1]+a[i].e;
		sg[i]=sg[i-1]+a[i].g;
	}
}
void FindL()
{
	a[n+1].x=inf;
	deque<lli> p;
	for(int i=1;i<=n;i++)
	{
		b[i]=b[i-1]-(a[i+1].x-a[i].x)+a[i].e;
	}
	for(int i=0;i<=n;i++)
	{
		while(!p.empty())
		{
			if(b[p.back()]>b[i])
			{
				r[p.back()+1]=i;
				p.pop_back();
			}
			else
			{
				break;
			}
		}
		p.push_back(i);
	}
	r[n]=n;
}
void FindR()
{
	b[n+1]=0;
	a[0].x=-inf;
	for(int i=n;i>=1;i--)
	{
		b[i]=b[i+1]+a[i].e-(a[i].x-a[i-1].x);
	}
	deque<lli> p;
	for(int i=n+1;i>=1;i--)
	{
		while(!p.empty())
		{
			if(b[p.back()]>b[i])
			{
				l[p.back()-1]=i;
				p.pop_back();
			}
			else
			{
				break;
			}
		}
		p.push_back(i);
	}
	l[1]=1;
}
struct T1
{
	lli l, r, x;
};
deque<T1> p, q;
void Fixed()
{
	for(int i=1;i<=n;i++)
	{
		r[i]=a[i].x+s[r[i]]-s[i-1];
		l[i]=a[i].x-(s[i]-s[l[i]-1]);
	}
	lli maxx=-inf, minn=inf;
	for(int i=1;i<=n;i++)
	{
		if(r[i]>maxx)
		{
			maxx=r[i];
			p.push_back({a[i].x, r[i], i});
		}
	}
	for(int i=n;i>=1;i--)
	{
		if(l[i]<minn)
		{
			minn=l[i];
			q.push_front({l[i], a[i].x, i});
		}
	}
}
void Solve()
{
	lli kq=0, s1=p.size(), s2=q.size(), v=0;
	for(int i=0;i<s1;i++)
	{
		while(v<s2)
		{
			if(q[v].l>p[i].r)
			{
				break;
			}
			v++;
		}
		kq=max(kq, sg[q[v-1].x]-sg[p[i].x-1]);
	}
	cout<<kq;
}
int main()
{
	//freopen("test.inp","r",stdin);
	Inp();
	FindL();
	FindR();
	Fixed();
	Solve();
}

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