Submission #234076

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
234076	2020-05-22T23:42:00 Z	hugo_pm	Editor (BOI15_edi)	C++17	100 / 100	112 ms	18680 KB

edi

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

using PQ = vector<int>; 
const int maxElem = 3e5 + 5;
PQ hidden[maxElem];
int level[maxElem];
int lastEdit[maxElem];
int parent[maxElem];
int lg[maxElem];
int nbElem;

bool comp(const int &a, const int &b) {
	return level[a] < level[b];
}

void merge(PQ &dest, PQ &eaten) {
	if (dest.size() < eaten.size()) swap(dest, eaten); 
	if (2*(int)dest.size() < lg[eaten.size()]) {
		dest.insert(dest.end(), eaten.begin(), eaten.end());
		make_heap(dest.begin(), dest.end());
		return;
	}
	for (int x : eaten) {
		dest.push_back(x);
		push_heap(dest.begin(), dest.end(), comp);
	}
}

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]);
	}

	for (int i = 2; i < maxElem; ++i) {
		lg[i] = lg[i/2] + 1;
	}

	PQ cur;
	for (int iElem = nbElem; iElem >= 1; --iElem) {
		PQ nxt;
		while (!cur.empty() && level[cur.front()] > level[iElem]) {
			parent[cur.front()] = iElem-1;
			merge(nxt, hidden[cur.front()]);
			pop_heap(cur.begin(), cur.end(), comp);
			cur.pop_back();
		}
		nxt.push_back(iElem);
		push_heap(nxt.begin(), nxt.end(), comp);
		merge(hidden[iElem], 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	8576 KB	Output is correct
2	Correct	10 ms	8704 KB	Output is correct
3	Correct	9 ms	8576 KB	Output is correct
4	Correct	9 ms	8576 KB	Output is correct
5	Correct	10 ms	8704 KB	Output is correct
6	Correct	9 ms	8576 KB	Output is correct
7	Correct	10 ms	8704 KB	Output is correct
8	Correct	9 ms	8576 KB	Output is correct
9	Correct	11 ms	8704 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	88 ms	16632 KB	Output is correct
2	Correct	93 ms	16632 KB	Output is correct

Subtask #3

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	13560 KB	Output is correct
2	Correct	55 ms	14364 KB	Output is correct
3	Correct	87 ms	12272 KB	Output is correct
4	Correct	92 ms	16592 KB	Output is correct
5	Correct	97 ms	17016 KB	Output is correct
6	Correct	67 ms	13428 KB	Output is correct

Subtask #4

37.0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	8576 KB	Output is correct
2	Correct	10 ms	8704 KB	Output is correct
3	Correct	9 ms	8576 KB	Output is correct
4	Correct	9 ms	8576 KB	Output is correct
5	Correct	10 ms	8704 KB	Output is correct
6	Correct	9 ms	8576 KB	Output is correct
7	Correct	10 ms	8704 KB	Output is correct
8	Correct	9 ms	8576 KB	Output is correct
9	Correct	11 ms	8704 KB	Output is correct
10	Correct	88 ms	16632 KB	Output is correct
11	Correct	93 ms	16632 KB	Output is correct
12	Correct	49 ms	13560 KB	Output is correct
13	Correct	55 ms	14364 KB	Output is correct
14	Correct	87 ms	12272 KB	Output is correct
15	Correct	92 ms	16592 KB	Output is correct
16	Correct	97 ms	17016 KB	Output is correct
17	Correct	67 ms	13428 KB	Output is correct
18	Correct	91 ms	18680 KB	Output is correct
19	Correct	89 ms	18428 KB	Output is correct
20	Correct	112 ms	13176 KB	Output is correct
21	Correct	90 ms	16632 KB	Output is correct
22	Correct	96 ms	17144 KB	Output is correct