제출 #155966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
155966		faremy	3단 점프 (JOI19_jumps)	C++14	100 / 100	1831 ms	90064 KiB

jumps

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <utility>


class Interval
{
	int left, right;

public:
	Interval(int l, int r) : left(l), right(r) {}

	bool IsIncludedIn(const Interval &other) const
	{
		return (other.left <= left && right <= other.right);
	}

	bool IsDisjointFrom(const Interval &other) const
	{
		return (other.right <= left || right <= other.left);
	}

	Interval Left() const
	{
		return Interval(left, (left + right) / 2);
	}

	Interval Right() const
	{
		return Interval((left + right) / 2, right);
	}
};

const int MAXN = 5e5;
const int LEAVES = 1 << 19;
const int TSIZE = LEAVES << 1;
const Interval ROOTCOVER = { 0, LEAVES };

int firmness[MAXN];
std::stack<int> useful;

std::vector<std::pair<int, int>> seg[MAXN];
std::vector<std::pair<int, int>> query[MAXN];

int maxFirm[TSIZE];
int bestScore[TSIZE], lazy[TSIZE];

int answer[MAXN];


void createusefulsegments(int positions)
{
	for (int iPos = 0; iPos < positions; iPos++)
	{
		while (!useful.empty() && firmness[useful.top()] < firmness[iPos])
		{
			seg[useful.top()].emplace_back(2 * iPos - useful.top(), firmness[iPos] + firmness[useful.top()]);
			useful.pop();
		}

		if (!useful.empty())
			seg[useful.top()].emplace_back(2 * iPos - useful.top(), firmness[iPos] + firmness[useful.top()]);
		useful.emplace(iPos);
	}
}

void setup(int positions)
{
	for (int iPos = 0; iPos < positions; iPos++)
		maxFirm[iPos + LEAVES] = firmness[iPos];
	for (int iNode = LEAVES - 1; iNode > 0; iNode--)
		maxFirm[iNode] = std::max(maxFirm[iNode * 2], maxFirm[iNode * 2 + 1]);
}

void push(int node)
{
	bestScore[node] = std::max(bestScore[node], maxFirm[node] + lazy[node]);
	if (node < LEAVES)
	{
		lazy[node * 2] = std::max(lazy[node * 2], lazy[node]);
		lazy[node * 2 + 1] = std::max(lazy[node * 2 + 1], lazy[node]);
	}
}

void update(int node, Interval covered, Interval requested, int value)
{
	push(node);
	if (covered.IsIncludedIn(requested))
	{
		lazy[node] = std::max(lazy[node], value);
		push(node);
	}
	else if (!covered.IsDisjointFrom(requested))
	{
		update(node * 2, covered.Left(), requested, value);
		update(node * 2 + 1, covered.Right(), requested, value);
		bestScore[node] = std::max(bestScore[node], std::max(bestScore[node * 2], bestScore[node * 2 + 1]));
	}
}

int request(int node, Interval covered, Interval requested)
{
	push(node);
	if (covered.IsIncludedIn(requested))
		return bestScore[node];
	if (covered.IsDisjointFrom(requested))
		return 0;
	return std::max(request(node * 2, covered.Left(), requested), request(node * 2 + 1, covered.Right(), requested));
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cout.tie(nullptr);
	std::cin.tie(nullptr);

	int positions; std::cin >> positions;
	for (int iPos = 0; iPos < positions; iPos++)
		std::cin >> firmness[iPos];
	
	createusefulsegments(positions);
	setup(positions);

	int queries; std::cin >> queries;
	for (int iQuery = 0; iQuery < queries; iQuery++)
	{
		int left, right;
		std::cin >> left >> right;
		query[left - 1].emplace_back(iQuery, right);
	}

	for (int iPos = positions - 1; iPos > -1; iPos--)
	{
		for (std::pair<int, int> &add : seg[iPos])
			if (add.first < positions)
				update(1, ROOTCOVER, Interval(add.first, positions), add.second);

		for (std::pair<int, int> &ask : query[iPos])
			answer[ask.first] = request(1, ROOTCOVER, Interval(iPos, ask.second));
	}

	for (int iQuery = 0; iQuery < queries; iQuery++)
		std::cout << answer[iQuery] << '\n';

	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54