Submission #205094

#	Time	Username	Problem	Language	Result	Execution time	Memory
205094		faremy	Editor (BOI15_edi)	C++14	43 / 100	132 ms	19188 KiB

edi

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


const int MAXN = 3e5 + 1;

int type[MAXN];
std::vector<int> state;

std::vector<int> ofRank[MAXN];
int skip[MAXN];
int paired[MAXN];


int jump(int pos)
{
	if (skip[pos] != pos)
		skip[pos] = jump(skip[pos]);
	return skip[pos];
}

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

	int ops; std::cin >> ops;
	for (int iOp = 1; iOp <= ops; iOp++)
	{
		std::cin >> type[iOp];
		if (type[iOp] < 0)
			ofRank[-type[iOp]].emplace_back(iOp);
		skip[iOp] = iOp;
	}

	for (int iRank = ops; iRank > 0; iRank--)
		for (int pos : ofRank[iRank])
		{
			if (skip[pos] != pos)
				continue;
			skip[pos] = jump(pos - 1);
			paired[pos] = skip[pos];
			skip[skip[pos]]--;
		}

	state.emplace_back(0);
	for (int iOp = 1; iOp <= ops; iOp++)
	{
		if (type[iOp] > 0)
		{
			state.emplace_back(iOp);
			skip[iOp] = iOp;
		}
		else if (type[paired[iOp]] > 0)
		{
			state.pop_back();
			skip[iOp] = paired[iOp] - 1;
		}
		else
		{
			if (paired[iOp] == 0)
				skip[iOp] = iOp - 1;
			else
				skip[iOp] = paired[iOp];
			int toggle = jump(iOp);

			if (state.back() == toggle)
				state.pop_back();
			else
				state.emplace_back(toggle);
		}

		std::cout << type[state.back()] << '\n';
	}

	return 0;
}

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