Submission #5422

#	Time	Username	Problem	Language	Result	Execution time	Memory
5422		gs12006	Divide and conquer (IZhO14_divide)	C++98	100 / 100	168 ms	8824 KiB

divide

#include <stdio.h>
#include <algorithm>
using namespace std;

long long int g[110000],l[110000],e[110000];

struct gw
{
	long long int x,e,w;
}a[220000];

bool cmp(gw x,gw y)
{
	if (x.e-l[x.x]==y.e-l[y.x]) return x.x<y.x;
	return x.e-l[x.x]<y.e-l[y.x]; 
}

int main()
{
	long long int n,i,se=0,ge=0,mini=1<<30,gmax=0;
	gw tgw;
	scanf("%lld",&n);
	for (i=0;i<n;i++)
	{
		scanf("%lld %lld %lld",&l[i+1],&g[i+1],&e[i+1]);
		g[i+1]+=ge;
		ge=g[i+1];
		e[i+1]+=se;
		se=e[i+1];
		tgw.e=e[i];
		tgw.x=i+1;
		tgw.w=0;
		a[2*i]=tgw;
		tgw.e=e[i+1];
		tgw.w=1;
		a[2*i+1]=tgw;
	}
	sort(a,a+2*n,cmp);
	for (i=0;i<2*n;i++)
	{
		if (a[i].w==0)
		{
			if (a[i].x<mini) mini=a[i].x;
		}
		else
		{
			if (g[a[i].x]-g[mini-1]>gmax) gmax=g[a[i].x]-g[mini-1];
		}
	}
	printf("%lld",gmax);
}

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