Submission #234086

#	Time	Username	Problem	Language	Result	Execution time	Memory
234086		hugo_pm	Editor (BOI15_edi)	C++17	100 / 100	133 ms	22136 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 nbElem;

int real[maxElem];
int fake[maxElem];

void merge(PQ &dest, PQ &eaten) {
	if (dest.size() < eaten.size()) swap(dest, eaten); 
	if (dest.size() < 8U*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());
	}
}

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

	sort(util.begin(), util.end());
	for (int i = 0; i < nbElem; ++i) {
		real[i] = util[i].second;
		fake[real[i]] = i;
	}

	PQ cur;
	for (int iElem = nbElem; iElem >= 1; --iElem) {
		PQ nxt;
		while (!cur.empty() && level[real[cur.front()]] > level[iElem]) {
			parent[real[cur.front()]] = iElem-1;
			merge(nxt, hidden[cur.front()]);
			pop_heap(cur.begin(), cur.end());
			cur.pop_back();
		}
		nxt.push_back(fake[iElem]);
		push_heap(nxt.begin(), nxt.end());
		merge(hidden[fake[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