Submission #234087

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
234087	2020-05-23T00:07:16 Z	hugo_pm	Editor (BOI15_edi)	C++17	100 / 100	100 ms	21752 KB

edi

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;

const int maxElem = 3e5 + 5;
int nbElem;
int level[maxElem];
int lastEdit[maxElem];
int parent[maxElem];

struct comp {
	bool operator()(int a, int b) {
		return level[a] < level[b];
	}
};
using PQ = priority_queue<int, vector<int>, comp>; 
PQ hidden[maxElem];

void merge(PQ &dest, PQ &eaten) {
	if (dest.size() < eaten.size()) dest.swap(eaten); 
	while (!eaten.empty()) {
		dest.push(eaten.top());
		eaten.pop();
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> nbElem;	
	for (int iElem = 1; iElem <= nbElem; ++iElem) {
		cin >> lastEdit[iElem];
		level[iElem] = max(0, -lastEdit[iElem]);
	}

	PQ cur;
	for (int iElem = nbElem; iElem >= 1; --iElem) {
		PQ nxt;
		while (!cur.empty() && level[cur.top()] > level[iElem]) {
			parent[cur.top()] = iElem-1;
			merge(nxt, hidden[cur.top()]);
			cur.pop();
		}
		nxt.push(iElem);
		hidden[iElem].swap(cur);
		cur.swap(nxt);
	}

	for (int iElem = 1; iElem <= nbElem; ++iElem) {
		if (level[iElem] > 0) {
			lastEdit[iElem] = lastEdit[parent[iElem]];
		}
		cout << lastEdit[iElem] << "\n";
	}
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	9728 KB	Output is correct
2	Correct	11 ms	9984 KB	Output is correct
3	Correct	9 ms	9728 KB	Output is correct
4	Correct	9 ms	9728 KB	Output is correct
5	Correct	10 ms	9984 KB	Output is correct
6	Correct	9 ms	9728 KB	Output is correct
7	Correct	10 ms	9856 KB	Output is correct
8	Correct	9 ms	9728 KB	Output is correct
9	Correct	10 ms	9984 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	91 ms	20064 KB	Output is correct
2	Correct	88 ms	20088 KB	Output is correct

Subtask #3

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	15736 KB	Output is correct
2	Correct	56 ms	16544 KB	Output is correct
3	Correct	81 ms	17136 KB	Output is correct
4	Correct	89 ms	20348 KB	Output is correct
5	Correct	96 ms	21112 KB	Output is correct
6	Correct	67 ms	19180 KB	Output is correct

Subtask #4

37.0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	9728 KB	Output is correct
2	Correct	11 ms	9984 KB	Output is correct
3	Correct	9 ms	9728 KB	Output is correct
4	Correct	9 ms	9728 KB	Output is correct
5	Correct	10 ms	9984 KB	Output is correct
6	Correct	9 ms	9728 KB	Output is correct
7	Correct	10 ms	9856 KB	Output is correct
8	Correct	9 ms	9728 KB	Output is correct
9	Correct	10 ms	9984 KB	Output is correct
10	Correct	91 ms	20064 KB	Output is correct
11	Correct	88 ms	20088 KB	Output is correct
12	Correct	50 ms	15736 KB	Output is correct
13	Correct	56 ms	16544 KB	Output is correct
14	Correct	81 ms	17136 KB	Output is correct
15	Correct	89 ms	20348 KB	Output is correct
16	Correct	96 ms	21112 KB	Output is correct
17	Correct	67 ms	19180 KB	Output is correct
18	Correct	89 ms	21752 KB	Output is correct
19	Correct	87 ms	21624 KB	Output is correct
20	Correct	100 ms	18928 KB	Output is correct
21	Correct	90 ms	20064 KB	Output is correct
22	Correct	97 ms	21152 KB	Output is correct