oj.uz

Submission #234078

# Submission time Handle Problem Language Result Execution time Memory
234078 2020-05-22T23:43:52 Z hugo_pm Editor (BOI15_edi) C++17
43 / 100
 104 ms 17044 KB 
#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 (dest.size() < 4U*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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8704 KB Output is correct
2 Incorrect 10 ms 8704 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 16572 KB Output is correct
2 Correct 96 ms 16632 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 13560 KB Output is correct
2 Correct 56 ms 14328 KB Output is correct
3 Correct 89 ms 12276 KB Output is correct
4 Correct 94 ms 16568 KB Output is correct
5 Correct 104 ms 17044 KB Output is correct
6 Correct 69 ms 13424 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8704 KB Output is correct
2 Incorrect 10 ms 8704 KB Output isn't correct
3 Halted 0 ms 0 KB -