Submission #204008

#	Time	Username	Problem	Language	Result	Execution time	Memory
204008		atoiz	Two Antennas (JOI19_antennas)	C++14	100 / 100	853 ms	44436 KiB

antennas

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

const int INF = 1e9 + 7;

void maximize(int &x, int y)
{ x = (x < y) ? y : x; }

struct SegmentTree
{
	struct Node
	{
		int finalMax, curMax, lazyRhs;

		Node(int _finalMax = -1, int _curMax = -1, int _lazyRhs = INF):
			finalMax(_finalMax), curMax(_curMax), lazyRhs(_lazyRhs) {}

		void updateRhs(int rhs)
		{
			if (lazyRhs > rhs) {
				maximize(finalMax, curMax - (lazyRhs = rhs));
			}
		}

		void push(Node &lChild, Node &rChild)
		{
			if (lazyRhs != INF) {
				lChild.updateRhs(lazyRhs);
				rChild.updateRhs(lazyRhs);
			}
			lazyRhs = INF;
		}

		void pull(Node &lhs, Node &rhs)
		{
			finalMax = max(lhs.finalMax, rhs.finalMax);
			curMax = max(lhs.curMax, rhs.curMax);
		}
	};

	int N;
	vector<Node> nodes;

	SegmentTree(int _N): N(_N)
	{
		nodes.assign(N * 4 + 7, Node());
	}

	void updateRhs(int l, int r, int rhs, int root, int lo, int hi)
	{
		if (hi < l || r < lo) return;
		if (l <= lo && hi <= r) {
			nodes[root].updateRhs(rhs);
			return;
		}

		nodes[root].push(nodes[root << 1], nodes[root << 1 | 1]);
		int mid = (lo + hi) >> 1;
		updateRhs(l, r, rhs, root << 1, lo, mid);
		updateRhs(l, r, rhs, root << 1 | 1, mid + 1, hi);
		nodes[root].pull(nodes[root << 1], nodes[root << 1 | 1]);
	}
	void updateRhs(int l, int r, int rhs)
	{ updateRhs(l, r, rhs, 1, 1, N); }

	void assignLhs(int pos, int lhs, int root, int lo, int hi)
	{
		if (lo == hi) {
			nodes[root].lazyRhs = INF;
			nodes[root].curMax = lhs;
			return;
		}

		nodes[root].push(nodes[root << 1], nodes[root << 1 | 1]);
		int mid = (lo + hi) >> 1;
		if (pos <= mid) assignLhs(pos, lhs, root << 1, lo, mid);
		else assignLhs(pos, lhs, root << 1 | 1, mid + 1, hi);
		nodes[root].pull(nodes[root << 1], nodes[root << 1 | 1]);
	}
	void assignLhs(int pos, int lhs)
	{ assignLhs(pos, lhs, 1, 1, N); }

	int getMax(int l, int r, int root, int lo, int hi)
	{
		if (hi < l || r < lo) return -1;
		if (l <= lo && hi <= r) return nodes[root].finalMax;

		nodes[root].push(nodes[root << 1], nodes[root << 1 | 1]);
		int mid = (lo + hi) >> 1;
		return max(
			getMax(l, r, root << 1, lo, mid),
			getMax(l, r, root << 1 | 1, mid + 1, hi)
		);
	}
	int getMax(int l, int r)
	{ return getMax(l, r, 1, 1, N); }
};

const int MAXN = 200006;
int N, Q;
int H[MAXN], A[MAXN], B[MAXN], ans[MAXN];
vector<pair<int, int>> queries[MAXN];
vector<int> add[MAXN], rem[MAXN];

void solve()
{
	SegmentTree st(N);
	for (int i = 1; i <= N; ++i) {
		for (int j : add[i]) st.assignLhs(j, H[j]);
		for (int j : rem[i]) st.assignLhs(j, -1);

		st.updateRhs(i - B[i], i - A[i], H[i]);
		for (auto q : queries[i]) maximize(ans[q.second], st.getMax(q.first, i));
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> H[i] >> A[i] >> B[i];

		add[min(i + A[i], N + 1)].push_back(i);
		rem[min(i + B[i] + 1, N + 1)].push_back(i);
	}

	cin >> Q;
	for (int i = 0; i < Q; ++i) {
		int l, r;
		cin >> l >> r;
		queries[r].emplace_back(l, i);
	}

	fill(ans, ans + Q, -1);
	solve();
	int maxH = *max_element(H + 1, H + 1 + N);
	for (int i = 1; i <= N; ++i) H[i] = maxH + 1 - H[i];
	solve();

	for (int i = 0; i < Q; ++i) {
		cout << ans[i] << '\n';
	}
}

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65