Submission #287828

#TimeUsernameProblemLanguageResultExecution timeMemory
287828zecookiezUntitled (POI11_rot)C++17
0 / 100
144 ms13388 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/detail/standard_policies.hpp> using namespace std; using namespace __gnu_pbds; template<class C>constexpr int len(const C&c){return int(c.size());} typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; const int MAXN = 200005; int N; 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; } vector<int> solve(){ int A; cin >> A; if(A != 0){ update(A, 1); return {A}; } vector<int> left = solve(), right = solve(); if(len(left) > len(right)) swap(left, right); long long cur, case1 = 0, case2 = 0; for(auto i : left) update(i, -1); 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); memset(bit, 0, sizeof(bit)); cin >> N; solve(); 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...