#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
struct BIT {
vector<int> tree;
int n;
void init(int _n) {
n = _n;
tree.assign(n+1,0);
}
void update(int pos,int val) {
for (;pos <= n;pos += pos & -pos) tree[pos] += val;
}
int query(int pos) {
int sum = 0;
for (;pos > 0;pos -= pos & -pos) sum += tree[pos];
return sum;
}
int query(int l,int r) {
if (l > r) return 0;
return query(r) - query(l-1);
}
} tree;
vector<int> adj[MAXN+1];
stack<pair<int,int>> st;
vector<int> ch[MAXN+1];
int val[MAXN+1];
int sz[MAXN+1];
int n;
int cnt;
long long ans = 0;
int cal_sz(int u) {
if (adj[u].size() == 0) return sz[u] = 1;
sz[u] += cal_sz(adj[u][0]);
sz[u] += cal_sz(adj[u][1]);
return sz[u];
}
void dfs(int u,int keep) {
if (adj[u].size() == 0) {
ch[u].push_back(val[u]);
if (keep) tree.update(val[u],1);
return;
}
int lt = adj[u][0], rt = adj[u][1];
long long tmp = 0;
if (sz[lt] < sz[rt]) {
dfs(lt,0);
dfs(rt,1);
ch[u].swap(ch[rt]);
for (int i=0;i<ch[lt].size();i++) {
int v = ch[lt][i];
ch[u].push_back(v);
// cerr << u << ' ' << v << '\n';
tmp += tree.query(1,v-1);
}
if (!keep) {
for (int i=0;i<ch[rt].size();i++) tree.update(ch[rt][i],-1);
}
else {
for (int i=0;i<ch[lt].size();i++) tree.update(ch[lt][i],1);
}
}
else {
dfs(rt,0);
dfs(lt,1);
ch[u].swap(ch[lt]);
for (int i=0;i<ch[rt].size();i++) {
int v = ch[rt][i];
// cerr << u << ' ' << v << '\n';
ch[u].push_back(v);
tmp += tree.query(v+1,n);
}
if (!keep) {
for (int i=0;i<ch[lt].size();i++) tree.update(ch[lt][i],-1);
}
else {
for (int i=0;i<ch[rt].size();i++) tree.update(ch[rt][i],1);
}
}
tmp = min(tmp,1ll * sz[lt] * sz[rt] - tmp);
ans += tmp;
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
cin >> n;
tree.init(n);
for (int i=1;;i++) {
cin >> val[i];
if (st.size()) adj[st.top().first].push_back(i);
if (val[i] != 0) cnt++;
if (val[i] != 0 && st.top().second == 2) st.pop();
else if (val[i] != 0) st.top().second++;
else {
st.push({i,1});
}
if (cnt == n) break;
}
cal_sz(1);
dfs(1,1);
cout << ans;
return 0;
}
Compilation message
rot.cpp: In function 'void dfs(int, int)':
rot.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i=0;i<ch[lt].size();i++) {
| ~^~~~~~~~~~~~~~
rot.cpp:63:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int i=0;i<ch[rt].size();i++) tree.update(ch[rt][i],-1);
| ~^~~~~~~~~~~~~~
rot.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int i=0;i<ch[lt].size();i++) tree.update(ch[lt][i],1);
| ~^~~~~~~~~~~~~~
rot.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i=0;i<ch[rt].size();i++) {
| ~^~~~~~~~~~~~~~
rot.cpp:80:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int i=0;i<ch[lt].size();i++) tree.update(ch[lt][i],-1);
| ~^~~~~~~~~~~~~~
rot.cpp:83:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int i=0;i<ch[rt].size();i++) tree.update(ch[rt][i],1);
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1046 ms |
27472 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1067 ms |
27472 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1064 ms |
27472 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1064 ms |
27728 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1043 ms |
28240 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1048 ms |
29520 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1057 ms |
31056 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1054 ms |
32840 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1056 ms |
34544 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1026 ms |
39240 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1053 ms |
37960 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
