Submission #1021935

#TimeUsernameProblemLanguageResultExecution timeMemory
1021935BuiDucManh123Untitled (POI11_rot)C++14
0 / 100
158 ms29012 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int N=4e5; vector <int> g[N+5]; int n,x,i=0,value[N+5],siz[N+5],ans[N+5],bit[N+5],a,b,l,r; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...