# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
234086 |
2020-05-22T23:52:36 Z |
hugo_pm |
Editor (BOI15_edi) |
C++17 |
|
133 ms |
22136 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 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";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7424 KB |
Output is correct |
2 |
Correct |
10 ms |
7680 KB |
Output is correct |
3 |
Correct |
8 ms |
7424 KB |
Output is correct |
4 |
Correct |
8 ms |
7424 KB |
Output is correct |
5 |
Correct |
10 ms |
7552 KB |
Output is correct |
6 |
Correct |
8 ms |
7424 KB |
Output is correct |
7 |
Correct |
10 ms |
7552 KB |
Output is correct |
8 |
Correct |
8 ms |
7424 KB |
Output is correct |
9 |
Correct |
10 ms |
7680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
118 ms |
20088 KB |
Output is correct |
2 |
Correct |
116 ms |
20296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
14840 KB |
Output is correct |
2 |
Correct |
70 ms |
15992 KB |
Output is correct |
3 |
Correct |
100 ms |
14964 KB |
Output is correct |
4 |
Correct |
121 ms |
20088 KB |
Output is correct |
5 |
Correct |
133 ms |
20472 KB |
Output is correct |
6 |
Correct |
84 ms |
17008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7424 KB |
Output is correct |
2 |
Correct |
10 ms |
7680 KB |
Output is correct |
3 |
Correct |
8 ms |
7424 KB |
Output is correct |
4 |
Correct |
8 ms |
7424 KB |
Output is correct |
5 |
Correct |
10 ms |
7552 KB |
Output is correct |
6 |
Correct |
8 ms |
7424 KB |
Output is correct |
7 |
Correct |
10 ms |
7552 KB |
Output is correct |
8 |
Correct |
8 ms |
7424 KB |
Output is correct |
9 |
Correct |
10 ms |
7680 KB |
Output is correct |
10 |
Correct |
118 ms |
20088 KB |
Output is correct |
11 |
Correct |
116 ms |
20296 KB |
Output is correct |
12 |
Correct |
61 ms |
14840 KB |
Output is correct |
13 |
Correct |
70 ms |
15992 KB |
Output is correct |
14 |
Correct |
100 ms |
14964 KB |
Output is correct |
15 |
Correct |
121 ms |
20088 KB |
Output is correct |
16 |
Correct |
133 ms |
20472 KB |
Output is correct |
17 |
Correct |
84 ms |
17008 KB |
Output is correct |
18 |
Correct |
123 ms |
22136 KB |
Output is correct |
19 |
Correct |
111 ms |
22008 KB |
Output is correct |
20 |
Correct |
119 ms |
16756 KB |
Output is correct |
21 |
Correct |
119 ms |
20088 KB |
Output is correct |
22 |
Correct |
133 ms |
20472 KB |
Output is correct |