Submission #13507

#	Time	Username	Problem	Language	Result	Execution time	Memory
13507		woqja125	Divide and conquer (IZhO14_divide)	C++98	100 / 100	85 ms	7336 KiB

divide

#include<stdio.h>
#include<algorithm>
long long max(long long a, long long b){return a>b?a:b;}
const int MAX = 100001;
int x[MAX];
long long g[MAX], d[MAX];
int loc[MAX];
struct mine
{
	long long d;
	int i;
	bool operator<(const mine &A) const {return d<A.d;}
}m[MAX];
void set(int x, long long v);
long long getmax(int f, int r);
void init(int x);
int main()
{
	int n;
	int i;
	scanf("%d", &n);
	for(i=1; i<=n; i++)
	{
		scanf("%d%lld%lld", x+i, g+i, d+i);
		g[i] += g[i-1];
		d[i] += d[i-1];
		m[i].d = d[i] - x[i];
		m[i].i = i;
	}
	std::sort(m+1, m+1+n);
	init(n);
	for(i=1; i<=n; i++)
	{
		loc[m[i].i] = i;
		set(i, g[m[i].i]);
	}
	long long ans = 0;
	mine t;
	for(i=1; i<=n; i++)
	{
		t.d = d[i-1] - x[i];
		int x = std::lower_bound(m+1, m+1+n, t) - m;
		ans = max(ans, getmax(x, n) - g[i-1]);
		set(loc[i], 0);
	}
	printf("%lld", ans);
	return 0;
}


int b;
long long IT[MAX*3];
void init(int x){for(b=1; b<x; b*=2);}
void set(int x, long long v)
{
	IT[x+=b] = v;
	while(x/=2) IT[x] = max(IT[x*2], IT[x*2+1]);
}
long long getmax(int f, int r)
{
	f+=b; r+=b;
	long long re = 0;
	while(f<r)
	{
		if(f%2 == 1) re = max(re, IT[f++]);
		if(r%2 == 0) re = max(re, IT[r--]);
		f/=2;
		r/=2;
	}
	if(f==r) re = max(re, IT[f]);
	return re;
}

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