Submission #98345

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
98345	2019-02-22T17:25:26 Z	luciocf	Divide and conquer (IZhO14_divide)	C++14	100 / 100	162 ms	8184 KB

divide

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;
const int inf = 1e9+10;

typedef long long ll;

int x[maxn], g[maxn], d[maxn];

ll s[maxn], p[maxn];

ll tree[4*maxn];

void build(int node, int l, int r)
{
	if (l == r)
	{
		tree[node] = s[l-1]-x[l];
		return;
	}

	int mid = (l+r)>>1;

	build(2*node, l, mid); build(2*node+1, mid+1, r);

	tree[node] = min(tree[2*node], tree[2*node+1]);
}

int query(int node, int l, int r, ll v)
{
	if (l == r)
	{
		if (tree[node] <= v) return l;
		return inf;
	}

	int mid = (l+r)>>1;

	if (tree[2*node] <= v) return query(2*node, l, mid, v);
	return query(2*node+1, mid+1, r, v);
}

int main(void)
{
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> x[i] >> g[i] >> d[i];

		s[i] = s[i-1]+(ll)d[i];
		p[i] = p[i-1]+(ll)g[i];
	}

	build(1, 1, n);

	ll ans = 0LL;

	for (int i = 1; i <= n; i++)
	{
		int pos = query(1, 1, n, s[i]-(ll)x[i]);

		if (pos != inf && pos <= i) ans = max(ans, p[i]-p[pos-1]);
	}

	cout << ans << "\n";
}

Subtask #1

17.0 / 17.0

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

Subtask #2

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	512 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	3 ms	420 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	4 ms	428 KB	Output is correct
8	Correct	4 ms	384 KB	Output is correct
9	Correct	4 ms	392 KB	Output is correct
10	Correct	6 ms	512 KB	Output is correct
11	Correct	12 ms	768 KB	Output is correct
12	Correct	13 ms	768 KB	Output is correct

Subtask #3

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	612 KB	Output is correct
2	Correct	10 ms	1024 KB	Output is correct
3	Correct	14 ms	1108 KB	Output is correct
4	Correct	71 ms	3812 KB	Output is correct
5	Correct	78 ms	4348 KB	Output is correct
6	Correct	162 ms	8184 KB	Output is correct
7	Correct	120 ms	6908 KB	Output is correct
8	Correct	149 ms	7064 KB	Output is correct
9	Correct	139 ms	6876 KB	Output is correct
10	Correct	133 ms	6856 KB	Output is correct
11	Correct	149 ms	7544 KB	Output is correct
12	Correct	150 ms	7548 KB	Output is correct