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>
#define int long long
using namespace std;
const int N=4e5;
vector <int> g[N+9];
int n,value[N+9],bit[N+9],ans[N+9],x,i,l,r,siz[N+9];
void input(){
cin>>x;
if(x){
value[i]=x;
return;
}
int k=i;
i++;
g[k].push_back(i);
input();
i++;
g[k].push_back(i);
input();
}
void update(int i, int val){
while(i<=N){
bit[i]+=val;
i+=i&-i;
}
}
int get(int i){
int val=0;
while(i>0){
val+=bit[i];
i-=i&-i;
}
return val;
}
void add(int i, int val){
if (value[i]){
update(value[i],val);
return;
}
add(g[i][0],val);
add(g[i][1],val);
}
void tinh(int i){
if (value[i]){
l+=get(value[i]);
r+=get(n)-get(value[i]);
return;
}
for (int x : g[i]) tinh(x);
}
void solve(int i){
if (value[i]){
siz[i]=1;
update(value[i],1);
return;
}
int x=g[i][0];
int y=g[i][1];
solve(x); ans[i]+=ans[x];
solve(y); ans[i]+=ans[y];
if (siz[x]>siz[y]) swap(x,y);
add(x,-1);
l=0;r=0;
tinh(x);
add(x,1);
ans[i]+=min(l,r);
siz[i]=siz[x]+siz[y];
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
input();
solve(0);
cout<<ans[0];
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... |