Submission #234076

#	Time	Username	Problem	Language	Result	Execution time	Memory
234076		hugo_pm	Editor (BOI15_edi)	C++17	100 / 100	112 ms	18680 KiB

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 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37