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;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 2e6 + 5;
int n, t, a[NMAX], lc[NMAX], rc[NMAX];
int rt[NMAX], l[NMAX], r[NMAX], s[NMAX], cnt;
ll ans, r1, r2;
void dfs(int x){
cin >> a[x];
if(!a[x]){
lc[x] = ++t; dfs(lc[x]);
rc[x] = ++t; dfs(rc[x]);
}
return;
}
int upd(int le, int ri, int k){
int ix = ++cnt;
s[ix] = 1;
if(le == ri) return ix;
int m = (le + ri) / 2;
if(k <= m) l[ix] = upd(le, m, k);
else r[ix] = upd(m + 1, ri, k);
return ix;
}
int merge(int x, int y){
if(!x) return y;
if(!y) return x;
r1 += s[l[x]] * s[r[y]];
r2 += s[l[y]] * s[r[x]];
l[x] = merge(l[x], l[y]);
r[x] = merge(r[x], r[y]);
s[x] = s[l[x]] + s[r[x]];
return x;
}
ll dfs2(int x){
if(a[x]) return 0;
ll ret = dfs2(lc[x]) + dfs2(rc[x]);
r1 = r2 = 0;
rt[x] = merge(rt[lc[x]], rt[rc[x]]);
ret += min(r1, r2);
return ret;
}
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
dfs(++t);
for(int i = 1; i <= t; i++)
if(a[i]) rt[i] = upd(1, n, a[i]);
cout << dfs2(1);
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... |