Submission #1067031

#TimeUsernameProblemLanguageResultExecution timeMemory
1067031vux2codeUntitled (POI11_rot)C++17
100 / 100
117 ms22612 KiB
// Src : Vux2Code #include <bits/stdc++.h> using namespace std; template <typename T> void vout(T s){ cout << s << endl; exit(0);} typedef long long ll; typedef long double ld; typedef pair <ll, ll> pll; // ll t = 1; const int mxn = 4e5 + 5; int tin[mxn], tout[mxn], l[mxn], r[mxn], pos[mxn], fwk[mxn]; long long sz[mxn], dp[mxn]; int cnt = 0, n, t = 0; void upd(int p, int val) { for (int i = p; i <= n; i += (i & -i)) { fwk[i] += val; } } int qry(int p) { int sum = 0; for (int i = p; i > 0; i -= (i & -i)) { sum += fwk[i]; } return sum; } int input() { int cur; cin >> cur; if (cur == 0) { cur = ++cnt; l[cur] = input(); r[cur] = input(); tin[cur] = tin[l[cur]]; tout[cur] = tout[r[cur]]; sz[cur] = sz[l[cur]] + sz[r[cur]]; } else { tin[cur] = tout[cur] = ++t; pos[t] = cur; sz[cur]++; } return cur; } void solve(int cur, bool keep) { if (cur <= n) { if (keep) { upd(pos[tin[cur]], 1); } return; } if (sz[l[cur]] < sz[r[cur]]) { swap(l[cur], r[cur]); } solve(r[cur], false); solve(l[cur], true); long long invcnt = 0; for (int i = tin[r[cur]]; i <= tout[r[cur]]; i++) { invcnt += qry(pos[i]); } dp[cur] = dp[l[cur]] + dp[r[cur]] + min(invcnt, (sz[l[cur]] * sz[r[cur]]) - invcnt); if (keep) { for (int i = tin[r[cur]]; i <= tout[r[cur]]; i++) { upd(pos[i], 1); } } else { for (int i = tin[l[cur]]; i <= tout[l[cur]]; i++) { upd(pos[i], -1); } } } void solve () { cin >> n; cnt = n; input(); solve(n + 1, true); cout << dp[n + 1]; } int main () { ios::sync_with_stdio (0); cin. tie (0); cout. tie (0); // #define TASK "task" // freopen (TASK".inp", "r", stdin); // freopen (TASK".out", "w", stdout); // cin >> t; // while (t --) solve (); solve (); }
#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...