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=0,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 cnt(int i){
if(value[i]){
siz[i]=1;
return;
}for(auto x:g[i]){
cnt(x);
siz[i]+=siz[x];
}
}
void update(int i, int val){
while(i<=N){
bit[i]+=val;
i+=i&-i;
}
}
int get(int i){
int val=0;
while(i){
val+=bit[i];
i-=i&-i;
}
return val;
}
void add(int i, int val){
if (value[i]){
update(value[i],val);
return;
}
for(auto x:g[i]){
add(x,val);
}
}
void tinh(int i){
if (value[i]){
l+=get(value[i]);
r+=get(n)-get(value[i]);
return;
}
for (auto x : g[i]) tinh(x);
}
void solve(int i){
if (value[i]){
update(value[i],1);
return;
}
for(auto x:g[i]){
solve(x);
ans[i]+=ans[x];
}int x=g[i][0];
int y=g[i][1];
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);
}
int32_t main(){
cin>>n;
input();
cnt(0);
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... |