oj.uz

Submission #171395

# Submission time Handle Problem Language Result Execution time Memory
171395 2019-12-28T15:18:36 Z Nightmar Divide and conquer (IZhO14_divide) C++17
100 / 100
 121 ms 7944 KB 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <iomanip>
 
#define SWS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define ppb pop_back
#define ft first
#define sd second
#define read freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)
#define files read; write
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
const int Z = (int)2e3 + 228;
const int N = (int)3e5 + 228;
const int INF = (int)1e9 + 228;
const int MOD = (int)1e9 + 7;
const ll LLINF = (ll)1e15 + 228;

struct kek
{
	ll x, g, d;
};

kek a[N];
ll t[4 * N], add[4 * N], pref[N];

void push(int v, int tl, int tr)
{
	if (tl != tr)
	{
		add[2 * v] += add[v];
		add[2 * v + 1] += add[v];
	}
	t[v] += add[v];
	add[v] = 0;
}

void update(int v, int tl, int tr, int l, int r, ll x)
{
	push(v, tl, tr);
	if (tl >= l && tr <= r)
	{
		add[v] = x;
		push(v, tl, tr);
		return;
	}
	if (tl > r || tr < l)
		return;
	int mid = (tl + tr) / 2;
	update(2 * v, tl, mid, l, r, x);
	update(2 * v + 1, mid + 1, tr, l, r, x);
	t[v] = max(t[2 * v], t[2 * v + 1]);
}

int get_r(int v, int tl, int tr)
{
	push(v, tl, tr);
	if (tl == tr)
		return tl;
	int mid = (tl + tr) / 2;
	if (t[2 * v + 1] + add[2 * v + 1] >= 0) return get_r(2 * v + 1, mid + 1, tr);
	else return get_r(2 * v, tl, mid);
}

int main()
{
	SWS;
	//files;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int x, g, d;
		cin >> x >> g >> d;
		a[i] = {x, g, d};
		pref[i] = pref[i - 1] + g;
	}
	ll ans = 0;
	for (int i = n; i > 0; i--)
	{
		if (i != n) update(1, 1, n, i + 1, n, a[i].x - a[i + 1].x);
		update(1, 1, n, i, n, a[i].d);
		int r = get_r(1, 1, n);
		ans = max(ans, pref[r] - pref[i - 1]);
	}
	cout << ans;
	return 0;
}
/*
*/

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 420 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 432 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 7 ms 888 KB Output is correct
12 Correct 7 ms 888 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 760 KB Output is correct
2 Correct 11 ms 1272 KB Output is correct
3 Correct 12 ms 1400 KB Output is correct
4 Correct 55 ms 4216 KB Output is correct
5 Correct 62 ms 4216 KB Output is correct
6 Correct 119 ms 7928 KB Output is correct
7 Correct 111 ms 7868 KB Output is correct
8 Correct 107 ms 7800 KB Output is correct
9 Correct 105 ms 7944 KB Output is correct
10 Correct 106 ms 7800 KB Output is correct
11 Correct 113 ms 7800 KB Output is correct
12 Correct 121 ms 7800 KB Output is correct