Submission #339486

#	Time	Username	Problem	Language	Result	Execution time	Memory
339486		_ani	Divide and conquer (IZhO14_divide)	C++17	100 / 100	202 ms	13292 KiB

divide

#define BUGO(x) cerr << #x << " = " << (x) << '\n';
#define BUGOARR(x) { cerr << "{ "; for(auto& i: (x))cerr<<i<<' ';cerr<<"}\n";}
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
const int N = 100'002;
ll x[N], g[N], e[N], prefe[N];
ll t[4 * N], lazy[4 * N], llazy[4 * N];
ll ans[N];
//Build
void Build(int v, int vl, int vr)
{
	if (vl == vr)
	{
		t[v] = prefe[vl];
		return;
	}
	int m = (vl + vr) / 2;
	Build(v, vl, m);
	Build(v, m + 1, vr);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}
inline void Push(int v, int vl, int vr)
{
	if (llazy[v] == 0)return;
	if (vl != vr)
	{
		llazy[v * 2] = llazy[v * 2 + 1] = 1;
		lazy[v * 2] += lazy[v];
		lazy[v * 2 + 1] += lazy[v];
	}
	t[v] += lazy[v];
	lazy[v] = llazy[v] = 0;
}
//Add
void Add(int v, int vl, int vr, int l, int r, ll val)
{
	if (vl == l && vr == r)
	{
		llazy[v] = 1;
		lazy[v] += val;
		return;
	}
	Push(v, vl, vr);
	int m = (vl + vr) / 2;
	if (l <= m)
		Add(v * 2, vl, m, l, min(r, m), val);
	if (r > m)
		Add(v * 2 + 1, m + 1, vr, max(l, m + 1), r, val);
	Push(v * 2, vl, m);
	Push(v * 2 + 1, m + 1, vr);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}
//FindLast
int FindLast(int v, int vl, int vr)
{
	Push(v, vl, vr);
	if (vl == vr)
	{
		if (t[v] < 0)
			return N;
		return vl;
	}
	int m = (vl + vr) / 2;
	Push(v * 2, vl, m);
	Push(v * 2 + 1, m + 1, vr);
	if (t[v * 2 + 1] >= 0)
		return FindLast(v * 2 + 1, m + 1, vr);
	return FindLast(v * 2, vl, m);
}
ll Get(int v, int vl, int vr, int pos)
{
	Push(v, vl, vr);
	if (vl == vr)
		return t[v];
	int m = (vl + vr) / 2;
	if (pos <= m)
		return Get(v * 2, vl, m, pos);
	return Get(v * 2 + 1, m + 1, vr, pos);
}
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x[i] >> g[i] >> e[i];
		prefe[i] = prefe[i - 1] + e[i];
		g[i] += g[i - 1];
	}
	Build(1, 1, n);
	for (int i = 1; i <= n; i++)
		Add(1, 1, n, i, i, -x[i] + prefe[i]);
	
	for (int i = 1; i <= n; i++)
	{
		Add(1, 1, n, i, n, -x[i - 1] + x[i] - e[i - 1]);
	/*	for (int i = 1; i <= n; i++)
			cout << Get(1, 1, n, i) << ' ';
		cout << '\n';
	*/	int ind = FindLast(1, 1, n);
		if (ind == N || ind < i)
		{
			ans[i] = 0;
			continue;
		}
		ans[i] = g[ind] - g[i - 1];
	}
	ll ma = 0;
	for (int i = 1; i <= n; i++)
	{
	//	cerr << ans[i] << ' ';
		ma = max(ma, ans[i]);
	}
//	cerr << '\n';
	cout << ma << '\n';
	return 0;
}

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