Submission #1298121

#TimeUsernameProblemLanguageResultExecution timeMemory
1298121arashmemarTwo Antennas (JOI19_antennas)C++20
22 / 100
368 ms54856 KiB
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 100, inf = 1e9 + 100;

int l[maxn], r[maxn], h[maxn], n;

vector <int> add[maxn], del[maxn];

struct Node
{
	int L, R, mid, v;
	Node *lc, *rc;

	Node (int l, int r)
	{
		L = l, R = r, mid = (L + R) / 2, v = inf, lc = rc = NULL;
	}

	void init()
	{
		if (R - L == 1)
		{
			return ;
		}
		lc = new Node(L, mid);
		rc = new Node(mid, R);
		lc->init();
		rc->init();
		return ;
	}

	void update(int p, int val)
	{
		if (R - L == 1)
		{
			v = val;
			return ;
		}
		if (p < mid)
		{
			lc->update(p, val);
		}
		else
		{
			rc->update(p, val);
		}
		v = min(lc->v, rc->v);
		return ;
	}

	int get(int l, int r)
	{
		if (l >= r)
		{
			return inf;
		}
		if (l == L and R == r)
		{
			return v;
		}
		int ret = inf;
		if (l < mid)
		{
			ret = min(ret, lc->get(l, min(r, mid)));
		}
		if (r > mid)
		{
			ret = min(ret, rc->get(max(l, mid), r));
		}
		return ret;
	}
};

int solve()
{
	int ret = -1;

	Node *root = new Node(1, n + 1);
	root->init();

	for (int i = n;i;i--)
	{
		for (auto o : add[i])
		{
			root->update(o, h[o]);
		}

		ret = max(ret, h[i] - root->get(min(n + 1, i + l[i]), min(n + 1, i + r[i] + 1)));

		for (auto o : del[i])
		{
			root->update(o, inf);
		}
		if (i - l[i] > 0)
		{
			add[i - l[i]].push_back(i);
		}
		if (i - r[i] > 0)
		{
			del[i - r[i]].push_back(i);
		}
	}
	for (int i = 1;i <= n;i++)
	{
		add[i].clear();
		del[i].clear();
	}
	return ret;
}

int main()
{
	cin >> n;
	for (int i = 1;i <= n;i++)
	{
		cin >> h[i] >> l[i] >> r[i];
	}

	int ans = solve();
	reverse(h + 1, h + 1 + n);
	reverse(l + 1, l + 1 + n);
	reverse(r + 1, r + 1 + n);
	ans = max(ans, solve());
	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...