Submission #145050

#	Time	Username	Problem	Language	Result	Execution time	Memory
145050		faremy	Global Warming (CEOI18_glo)	C++14	100 / 100	503 ms	9432 KiB

glo

#include <iostream>
#include <algorithm>
#include <set>


struct Seq
{
	Seq(int v, int s) : maxVal(v), size(s) {}
	int maxVal, size;
	
	bool operator <(const Seq &other) const
	{
		return (maxVal < other.maxVal);
	}
};

const int MAXN = 2e5;

int temp[MAXN];
int lis[MAXN], lds[MAXN];

std::set<Seq> stacket;


void insert(Seq sequence)
{
	while (stacket.lower_bound(sequence) != stacket.end() && stacket.lower_bound(sequence)->size <= sequence.size)
		stacket.erase(stacket.lower_bound(sequence));
	std::set<Seq>::iterator prev = stacket.upper_bound(sequence);

	prev--;
	if (prev->size < sequence.size)
		stacket.emplace(sequence);
}

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

	int days, maxOffset;
	std::cin >> days >> maxOffset;

	for (int iDay = 0; iDay < days; iDay++)
		std::cin >> temp[iDay];

	stacket.emplace(0, 0);
	for (int iDay = 0; iDay < days; iDay++)
	{
		std::set<Seq>::iterator prev = stacket.lower_bound(Seq(temp[iDay], 1));
		prev--;
		lis[iDay] = prev->size + 1;
		insert(Seq(temp[iDay], lis[iDay]));
	}

	stacket.clear();

	stacket.emplace(-2e9, 0);
	for (int iDay = days - 1; iDay > -1; iDay--)
	{
		std::set<Seq>::iterator prev = stacket.lower_bound(Seq(-temp[iDay], 1));
		prev--;
		lds[iDay] = prev->size + 1;
		insert(Seq(-temp[iDay], lds[iDay]));
	}

	stacket.clear();
	int maxLength = 1;

	stacket.emplace(0, 0);
	for (int iDay = 0; iDay < days; iDay++)
	{
		std::set<Seq>::iterator prev = stacket.lower_bound(Seq(temp[iDay] + maxOffset, 1));
		prev--;
		maxLength = std::max(maxLength, prev->size + lds[iDay]);
		insert(Seq(temp[iDay], lis[iDay]));
	}

	std::cout << maxLength << '\n';

	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25