Submission #1022465

#TimeUsernameProblemLanguageResultExecution timeMemory
1022465BuiDucManh123Untitled (POI11_rot)C++17
100 / 100
292 ms44256 KiB
#include <bits/stdc++.h> #define fi first #define se second #define ll long long #define ull unsigned long long #define pii pair<int, int> #define pll pair<ll, ll> #define pb push_back #define int long long using namespace std; const int N=8e5+5; int bit[N],sz[N],value[N],id=0,n,ans[N]; vector<int>g[N]; void input(){ int x; cin>>x; value[id]=x; if (x) return; int k=id; g[k].push_back(++id); input(); g[k].push_back(++id); input(); } int getSum(int p) { int idx = p, res = 0; while (idx > 0) { res += bit[idx]; idx -= (idx & (-idx)); } return res; } void update(int u, int v) { int idx = u; while (idx <= N) { bit[idx] += v; idx += (idx & (-idx)); } } void cnt(int id){ if(value[id]){ sz[id]=1; return; }for(int x:g[id]){ cnt(x); sz[id]+=sz[x]; }return; } void add(int id, int val){ if(value[id]){ update(value[id],val); return; }for(int x:g[id]) add(x,val); }int l,r; void cal(int id){ if(value[id]){ l+=getSum(value[id]); r+=getSum(n)-getSum(value[id]); return; }for(int x:g[id]) cal(x); } void solve(int id){ if(value[id]){ update(value[id],1); return; }int x=g[id][0]; int y=g[id][1]; if(sz[x]>sz[y]) swap(x,y); solve(x); ans[id]+=ans[x]; add(x,-1); solve(y); ans[id]+=ans[y]; l=0;r=0; cal(x); add(x,1); ans[id]+=min(l,r); return; } signed main() { cin>>n; input(); cnt(0); 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...