Submission #615856

#TimeUsernameProblemLanguageResultExecution timeMemory
6158561binUntitled (POI11_rot)C++14
100 / 100
366 ms23928 KiB
#include <bits/stdc++.h> using namespace std; #define all(v) v.begin(), v.end() typedef long long ll; const int base = 1 << 20; ll n, a[base], lc[base], rc[base], w[base], t, ans; ll seg[1 << 21]; void dfs(int x){ cin >> a[x]; if(a[x]) w[x] = 1; else{ lc[x] = ++t; dfs(lc[x]); rc[x] = ++t; dfs(rc[x]); if(w[lc[x]] > w[rc[x]]) swap(lc[x], rc[x]); w[x] = w[lc[x]] + w[rc[x]]; } return; } void upd(int idx, ll v){ idx += base; while(idx){ seg[idx] += v; idx /= 2; } return; } ll sum(int l, int r){ ll ret = 0; l += base; r += base; while(l <= r){ if(l & 1) ret += seg[l++]; if(!(r & 1)) ret += seg[r--]; l /= 2; r /= 2; } return ret; } void f(int x, int v){ if(a[x]){ upd(a[x], v); return; } f(lc[x], v); f(rc[x], v); return; } ll cal(int x){ if(a[x]) return sum(a[x] + 1, base - 1); return cal(lc[x]) + cal(rc[x]); } void dfs2(int x){ if(a[x]) { upd(a[x], 1); return; } ll v = 0; dfs2(lc[x]); f(lc[x], -1); dfs2(rc[x]); v += cal(lc[x]); f(lc[x], 1); ans += min(v, w[lc[x]] * w[rc[x]] - v); return; } int main(void){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; dfs(++t); dfs2(1); cout << ans; 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...