oj.uz

Submission #208981

# Submission time Handle Problem Language Result Execution time Memory
208981 2020-03-12T20:47:29 Z faremy Editor (BOI15_edi) C++14
100 / 100
 113 ms 30716 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19192 KB Output is correct
2 Correct 18 ms 19320 KB Output is correct
3 Correct 16 ms 19192 KB Output is correct
4 Correct 16 ms 19192 KB Output is correct
5 Correct 17 ms 19320 KB Output is correct
6 Correct 17 ms 19192 KB Output is correct
7 Correct 17 ms 19320 KB Output is correct
8 Correct 16 ms 19192 KB Output is correct
9 Correct 17 ms 19320 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 30072 KB Output is correct
2 Correct 94 ms 30072 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 24184 KB Output is correct
2 Correct 62 ms 24952 KB Output is correct
3 Correct 91 ms 25712 KB Output is correct
4 Correct 97 ms 30072 KB Output is correct
5 Correct 107 ms 30716 KB Output is correct
6 Correct 73 ms 26736 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19192 KB Output is correct
2 Correct 18 ms 19320 KB Output is correct
3 Correct 16 ms 19192 KB Output is correct
4 Correct 16 ms 19192 KB Output is correct
5 Correct 17 ms 19320 KB Output is correct
6 Correct 17 ms 19192 KB Output is correct
7 Correct 17 ms 19320 KB Output is correct
8 Correct 16 ms 19192 KB Output is correct
9 Correct 17 ms 19320 KB Output is correct
10 Correct 103 ms 30072 KB Output is correct
11 Correct 94 ms 30072 KB Output is correct
12 Correct 58 ms 24184 KB Output is correct
13 Correct 62 ms 24952 KB Output is correct
14 Correct 91 ms 25712 KB Output is correct
15 Correct 97 ms 30072 KB Output is correct
16 Correct 107 ms 30716 KB Output is correct
17 Correct 73 ms 26736 KB Output is correct
18 Correct 98 ms 29564 KB Output is correct
19 Correct 91 ms 28920 KB Output is correct
20 Correct 113 ms 27464 KB Output is correct
21 Correct 98 ms 30072 KB Output is correct
22 Correct 110 ms 30712 KB Output is correct