#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ld = long double;
using pll = pair<ll, ll>;
// and so on
struct bit {
int* tree;
int siz = 0;
vector<int> v;
void init(int x) {
for (siz = 1; siz < x; siz <<= 1)
;
if(!tree) tree = new int[siz + 1];
v.clear();
for (int i = 0; i <= siz; i++) tree[i] = 0;
}
void add(int pos, int x) {
v.push_back(pos);
while (pos <= siz) {
tree[pos] += x;
pos += (pos & -pos);
}
}
int sum(int pos) {
int ret = 0;
if(pos<=0) return 0;
while (pos) {
ret += tree[pos];
pos &= (pos - 1);
}
return ret;
}
};
bit st[200001];
stack<int> pool;
pll sol() {
ll c, ret = 0;
cin >> c;
if (c == 0) {
auto [sl, a] = sol();
auto [sr, b] = sol();
ret += sl + sr;
if(st[a].v.size() < st[b].v.size()) swap(a, b);
ll acnt = 0, bcnt = 0;
int siz = st[a].v.size();
for(auto x : st[b].v){
int cnt = st[a].sum(x-1);
acnt += cnt;
bcnt += siz - cnt;
}
ret += min(acnt, bcnt);
for(auto x : st[b].v){
st[a].add(x, 1);
}
pool.push(b);
return {ret, a};
} else {
int idx = pool.top();
pool.pop();
st[idx].init(200000);
st[idx].add(c, 1);
return {0, idx};
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for(int i=N-1;i>=0;i--) pool.push(i);
auto [ans, idx] = sol();
cout<<ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
14292 KB |
Output is correct |
2 |
Correct |
21 ms |
15288 KB |
Output is correct |
3 |
Correct |
21 ms |
14228 KB |
Output is correct |
4 |
Correct |
21 ms |
13252 KB |
Output is correct |
5 |
Correct |
7 ms |
10196 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
80 ms |
16376 KB |
Output is correct |
2 |
Correct |
95 ms |
38920 KB |
Output is correct |
3 |
Correct |
101 ms |
20496 KB |
Output is correct |
4 |
Correct |
96 ms |
32768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
536 ms |
31800 KB |
Output is correct |
2 |
Correct |
648 ms |
30820 KB |
Output is correct |
3 |
Correct |
602 ms |
19476 KB |
Output is correct |
4 |
Runtime error |
69 ms |
65536 KB |
Execution killed with signal 9 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
375 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
85 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
70 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
69 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
66 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1088 ms |
20308 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
70 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
70 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |