Submission #287846

#TimeUsernameProblemLanguageResultExecution timeMemory
287846zecookiezUntitled (POI11_rot)C++17
36 / 100
1090 ms21496 KiB
#include <bits/stdc++.h> using namespace std; template<class C>constexpr int len(const C&c){return int(c.size());} const int MAXN = 200005; int N, inp[MAXN], sz[MAXN], L[MAXN], R[MAXN]; long long ans, bit[MAXN]; void update(int pos, int val){ for(int i = pos; i <= N; i += i & -i) bit[i] += val; } long long query(int pos){ long long tot = 0; for(int i = pos; i > 0; i -= i & -i) tot += bit[i]; return tot; } int read_tree(int id){ cin >> inp[id]; if(inp[id] != 0){ L[id] = id; R[id] = id; sz[id] = 1; return id; } int left = read_tree(id + 1); int right = read_tree(left + 1); sz[id] = sz[left] + sz[right]; L[id] = left; R[id] = right; return right; } vector<int> solve(int id){ int A = inp[id]; if(A != 0){ update(A, 1); return {A}; } vector<int> left, right; if(sz[L[id]] <= sz[R[id]]){ left = solve(id + 1); for(auto i : left) update(i, -1); right = solve(L[id] + 1); } else { left = solve(L[id] + 1); for(auto i : left) update(i, -1); right = solve(id + 1); } long long cur, case1 = 0, case2 = 0; for(auto i : left){ cur = query(i - 1); case1 += cur; case2 += len(right) - cur; } ans += min(case1, case2); for(auto i : left) update(i, 1), right.push_back(i); return right; } int main(){ cin.sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; read_tree(0); solve(0); cout << ans << '\n'; 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...