제출 #208981

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
208981		faremy	Editor (BOI15_edi)	C++14	100 / 100	113 ms	30716 KiB

edi

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


struct Op
{
	Op(int i, int r) : id(i), rank(r) {}
	int id, rank;

	bool operator <(const Op &other) const
	{
		return (rank < other.rank);
	}
};

const int MAXN = 3e5 + 1;

int type[MAXN];
int rank[MAXN];

std::stack<int> alone;
std::priority_queue<Op> keep[MAXN];
std::priority_queue<Op> prison[MAXN];

int parent[MAXN];
int lastZero[MAXN];
std::stack<int> state;


void merge(std::priority_queue<Op> &a, std::priority_queue<Op> &b)
{
	if (a.size() < b.size())
		std::swap(a, b);
	while (!b.empty())
	{
		a.emplace(b.top());
		b.pop();
	}
}

int findzero(int node)
{
	if (lastZero[node] != -1)
		return lastZero[node];
	if (parent[node] != -1)
		lastZero[node] = findzero(parent[node]);
	if (rank[node] == 0)
		lastZero[node] = node;
	return lastZero[node];
}

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

	int ops; std::cin >> ops;
	for (int iOp = 0; iOp < ops; iOp++)
	{
		std::cin >> type[iOp];
		if (type[iOp] < 0)
			rank[iOp] = -type[iOp];
		parent[iOp] = -1;
		lastZero[iOp] = -1;
	}

	rank[ops] = -1;
	alone.emplace(ops);

	for (int iOp = ops - 1; iOp > -1; iOp--)
	{
		int pair = alone.top();
		std::vector<int> free;

		while (!keep[pair].empty() && keep[pair].top().rank > rank[iOp])
		{
			free.emplace_back(keep[pair].top().id);
			keep[pair].pop();
		}

		if (rank[pair] > rank[iOp])
		{
			merge(prison[iOp], keep[pair]);
			parent[pair] = iOp;
			alone.pop();
			keep[alone.top()].emplace(iOp, rank[iOp]);
		}
		else
		{
			alone.emplace(iOp);
		}

		for (int lock : free)
		{
			merge(keep[alone.top()], prison[lock]);
			parent[lock] = iOp;
		}
	}

	state.emplace(ops);
	for (int iOp = 0; iOp < ops; iOp++)
	{
		int toggle = findzero(iOp);
		if (state.top() == toggle)
			state.pop();
		else
			state.emplace(toggle);
		std::cout << type[state.top()] << '\n';
	}

	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37