oj.uz

Submission #13507

# Submission time Handle Problem Language Result Execution time Memory
13507 2015-02-22T05:33:51 Z woqja125 Divide and conquer (IZhO14_divide) C++
100 / 100
 85 ms 7336 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7336 KB Output is correct
2 Correct 0 ms 7336 KB Output is correct
3 Correct 0 ms 7336 KB Output is correct
4 Correct 0 ms 7336 KB Output is correct
5 Correct 0 ms 7336 KB Output is correct
6 Correct 0 ms 7336 KB Output is correct
7 Correct 0 ms 7336 KB Output is correct
8 Correct 0 ms 7336 KB Output is correct
9 Correct 0 ms 7336 KB Output is correct
10 Correct 0 ms 7336 KB Output is correct
11 Correct 0 ms 7336 KB Output is correct
12 Correct 0 ms 7336 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7336 KB Output is correct
2 Correct 0 ms 7336 KB Output is correct
3 Correct 0 ms 7336 KB Output is correct
4 Correct 0 ms 7336 KB Output is correct
5 Correct 0 ms 7336 KB Output is correct
6 Correct 0 ms 7336 KB Output is correct
7 Correct 0 ms 7336 KB Output is correct
8 Correct 0 ms 7336 KB Output is correct
9 Correct 0 ms 7336 KB Output is correct
10 Correct 2 ms 7336 KB Output is correct
11 Correct 2 ms 7336 KB Output is correct
12 Correct 5 ms 7336 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7336 KB Output is correct
2 Correct 8 ms 7336 KB Output is correct
3 Correct 8 ms 7336 KB Output is correct
4 Correct 37 ms 7336 KB Output is correct
5 Correct 48 ms 7336 KB Output is correct
6 Correct 59 ms 7336 KB Output is correct
7 Correct 85 ms 7336 KB Output is correct
8 Correct 77 ms 7336 KB Output is correct
9 Correct 42 ms 7336 KB Output is correct
10 Correct 84 ms 7336 KB Output is correct
11 Correct 74 ms 7336 KB Output is correct
12 Correct 83 ms 7336 KB Output is correct