Submission #765870

#TimeUsernameProblemLanguageResultExecution timeMemory
765870SeDunionUntitled (POI11_rot)C++17
0 / 100
114 ms7652 KiB
#include <iostream> #include <vector> #include <cmath> using namespace std; using ll = long long; const int N = 1e6 + 123; int l[N], r[N], temp, sz[N]; int build() { int v = temp++; int x; cin >> x; if (x) { sz[v] = 1; l[v] = r[v] = x; // cout << v << " " << l[v] << " " << r[v] << endl; return v; } l[v] = build(); r[v] = build(); sz[v] = sz[l[v]] + sz[r[v]] + 1; // cout << v << " " << l[v] << " " << r[v] << endl; return v; } int f[N]; void upd(int v, int t) { while (v < N) f[v] += t, v |= v + 1; } int get(int v) { int r = 0; while (v >= 0) r += f[v], v &= v + 1, v--; return r; } void clr(int v) { if (l[v] == r[v]) upd(l[v], -1); else clr(l[v]), clr(r[v]); } ll ans; void calc(int v) { if (l[v] == r[v]) temp += get(l[v]); else calc(l[v]), calc(r[v]); } void add(int v) { if (l[v] == r[v]) upd(l[v], +1); else add(l[v]), add(r[v]); } void dfs(int v, int type) { // return; // cout << v << endl; if (l[v] != r[v]) { if (sz[l[v]] > sz[r[v]]) { dfs(r[v], 1); dfs(l[v], 0); temp = 0; calc(r[v]); add(r[v]); } else { dfs(l[v], 1); dfs(r[v], 0); temp = 0; calc(l[v]); add(l[v]); } ll cost = min(sz[l[v]] * 1ll * sz[r[v]] - temp, 1ll * temp); // cout << v << " " << cost << " " << temp << " cost" << endl; ans += cost; } else { upd(l[v], +1); } if (type == 1) { clr(v); } } int main() { ios_base::sync_with_stdio(0), cin.tie(0); int n; cin >> n; dfs(build(), 0); cout << ans; }
#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...