Submission #234087

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

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