This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
dfs(lt,1);
dfs(rt,1);
// 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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |