# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
802835 |
2023-08-02T14:58:29 Z |
Arturgo |
Editor (BOI15_edi) |
C++14 |
|
143 ms |
64960 KB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>
struct Node {
T data;
vector<Node<T>*> children;
};
template<typename T>
Node<T>* merge(Node<T>* a, Node<T>* b) {
if(a->data > b->data) {
a->children.push_back(b);
return a;
}
b->children.push_back(a);
return b;
}
const int N_BITS = 20;
template<typename T>
using Heap = array<Node<T>*, N_BITS>;
template<typename T>
Heap<T> merge(Heap<T>& a, Heap<T>& b) {
Node<T>* reste = NULL;
Heap<T> nouv;
nouv.fill(NULL);
for(int iBit = 0;iBit < N_BITS;iBit++) {
if(reste == NULL) {
if(a[iBit] == NULL)
nouv[iBit] = b[iBit];
else if(b[iBit] == NULL)
nouv[iBit] = a[iBit];
else
reste = merge(a[iBit], b[iBit]);
}
else {
if(a[iBit] == NULL && b[iBit] == NULL) {
nouv[iBit] = reste;
reste = NULL;
}
else if(b[iBit] == NULL) {
nouv[iBit] = merge(reste, a[iBit]);
reste = NULL;
}
else if(a[iBit] == NULL) {
nouv[iBit] = merge(reste, b[iBit]);
reste = NULL;
}
else {
nouv[iBit] = reste;
reste = merge(a[iBit], b[iBit]);
}
}
}
return nouv;
}
pair<int, int> def = {-1e8, -1e8};
template<typename T>
T top(Heap<T>& a) {
T opt = def;
for(int iBit = 0;iBit < N_BITS;iBit++) {
if(a[iBit] != NULL) {
if(a[iBit]->data > opt) {
opt = a[iBit]->data;
}
}
}
return opt;
}
template<typename T>
void pop(Heap<T>& a) {
T opt = def;
int bitOpt = -1;
for(int iBit = 0;iBit < N_BITS;iBit++) {
if(a[iBit] != NULL) {
if(a[iBit]->data > opt) {
opt = a[iBit]->data;
bitOpt = iBit;
}
}
}
Heap<T> nouv;
nouv.fill(NULL);
for(int iChild = 0;iChild < (int)a[bitOpt]->children.size();iChild++) {
nouv[iChild] = a[bitOpt]->children[iChild];
}
delete a[bitOpt];
a[bitOpt] = NULL;
a = merge(a, nouv);
}
template<typename T>
void push(Heap<T>& a, T elem) {
Heap<T> nouv;
nouv.fill(NULL);
Node<T>* n = new Node<T>();
n->data = elem;
nouv[0] = n;
a = merge(a, nouv);
}
const int N = 3e5 + 42;
int n, lvl[N], par[N], val[N];
Heap<pair<int, int>> hid[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 0; i < n; i++) {
cin >> lvl[i];
lvl[i] = -lvl[i];
}
Heap<pair<int, int>> cur, nxt;
cur.fill(NULL);
nxt.fill(NULL);
for(int i = n-1; i > -1; i--) {
par[i] = i;
cur = nxt;
nxt = Heap<pair<int, int>>();
nxt.fill(NULL);
push(nxt, {max(lvl[i], 0ll), i});
while(true) {
pair<int, int> p = top(cur);
if(p.first <= max(lvl[i], 0ll))
break;
int id = p.second;
pop(cur);
par[id] = i;
nxt = merge(nxt, hid[id]);
}
swap(cur, hid[i]);
}
for(int i = 0; i < n; i++) {
if(lvl[i] < 0)
cout << (val[i] = -lvl[i]) << '\n';
else if(par[i] == 0) {
cout << 0 << '\n';
}
else {
cout << (val[i] = val[par[i]-1]) << '\n';
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
1364 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
3 ms |
1364 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
1364 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
3 ms |
1364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
129 ms |
64920 KB |
Output is correct |
2 |
Correct |
138 ms |
64928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
31692 KB |
Output is correct |
2 |
Correct |
72 ms |
38004 KB |
Output is correct |
3 |
Correct |
140 ms |
49008 KB |
Output is correct |
4 |
Correct |
129 ms |
64876 KB |
Output is correct |
5 |
Correct |
131 ms |
64668 KB |
Output is correct |
6 |
Correct |
113 ms |
64912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
1364 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
3 ms |
1364 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
1364 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
3 ms |
1364 KB |
Output is correct |
10 |
Correct |
129 ms |
64920 KB |
Output is correct |
11 |
Correct |
138 ms |
64928 KB |
Output is correct |
12 |
Correct |
65 ms |
31692 KB |
Output is correct |
13 |
Correct |
72 ms |
38004 KB |
Output is correct |
14 |
Correct |
140 ms |
49008 KB |
Output is correct |
15 |
Correct |
129 ms |
64876 KB |
Output is correct |
16 |
Correct |
131 ms |
64668 KB |
Output is correct |
17 |
Correct |
113 ms |
64912 KB |
Output is correct |
18 |
Correct |
127 ms |
63276 KB |
Output is correct |
19 |
Correct |
121 ms |
63320 KB |
Output is correct |
20 |
Correct |
143 ms |
61132 KB |
Output is correct |
21 |
Correct |
122 ms |
64960 KB |
Output is correct |
22 |
Correct |
129 ms |
64716 KB |
Output is correct |