Submission #287867

#TimeUsernameProblemLanguageResultExecution timeMemory
287867zecookiezUntitled (POI11_rot)C++17
0 / 100
1097 ms9336 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, id, cur, arr[MAXN], L[2*MAXN], R[2*MAXN], LL[2*MAXN], RR[2*MAXN], bit[MAXN]; long long ans; void update(int pos, int val){ for(int i = pos; i <= N; i += i & -i) bit[i] += val; } int query(int pos){ int tot = 0; for(int i = pos; i > 0; i &= i - 1) tot += bit[i]; return tot; } void read_tree(int node){ int A; cin >> A; L[node] = cur; if(A != 0){ arr[cur++] = A; R[node] = cur; return; } LL[node] = ++id; read_tree(id); RR[node] = ++id; read_tree(id); R[node] = cur; } void solve(int id){ if(R[id] - L[id] == 1){ update(arr[L[id]], 1); return; } int SZ, left = LL[id], right = RR[id], cur, case1 = 0, case2 = 0; int A = L[left], B = R[left], C = L[right], D = R[right]; if(B - A <= D - C){ solve(id + 1); for(int i = A; i < B; ++i) update(arr[i], -1); solve(left + 1); SZ = D - C; for(int i = A; i < B; ++i){ cur = query(arr[i] - 1); case1 += cur; case2 += SZ - cur; } for(int i = A; i < B; ++i) update(arr[i], 1); } else { solve(left + 1); for(int i = C; i < D; ++i) update(arr[i], -1); solve(id + 1); SZ = B - A; for(int i = C; i < D; ++i){ cur = query(arr[i] - 1); case1 += cur; case2 += SZ - cur; } for(int i = C; i < D; ++i) update(arr[i], 1); } ans += min(case1, case2); } 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...