Submission #615849

#TimeUsernameProblemLanguageResultExecution timeMemory
6158491binUntitled (POI11_rot)C++14
63 / 100
288 ms34436 KiB
#include <bits/stdc++.h> using namespace std; #define all(v) v.begin(), v.end() typedef long long ll; const int NMAX = 1e6 + 5; const int base = 1 << 20; int n, a[NMAX], lc[NMAX], rc[NMAX], w[NMAX], t; int seg[1 << 21]; vector<int> adj[NMAX]; ll ans; 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, int 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); ll ret = cal(lc[x]); ret += cal(rc[x]); return ret; } 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...