Submission #1085214

#TimeUsernameProblemLanguageResultExecution timeMemory
1085214eysbutnoUntitled (POI11_rot)C++17
27 / 100
93 ms65536 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = array<int, 2>; #define all(x) begin(x), end(x) #define sz(x) (int) (x).size() #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; int main() { cin.tie(0) -> sync_with_stdio(0); int n; cin >> n; int timer = 0; vector<ll> inv(3 * n); vector<Tree<int>> sets(3 * n); const auto dfs = [&](int idx, auto &&self) -> void { int x; cin >> x; if (x == 0) { int idx_l = ++timer; self(idx_l, self); int idx_r = ++timer; self(idx_r, self); if (sz(sets[idx_l]) > sz(sets[idx_r])) { sets[idx_l].swap(sets[idx_r]); } ll opt_1 = 0, opt_2 = 0; for (int v : sets[idx_l]) { int loc = sets[idx_r].order_of_key(v); opt_1 += loc; opt_2 += sz(sets[idx_r]) - loc; } for (int v : sets[idx_l]) { sets[idx_r].insert(v); } sets[idx_l].clear(); inv[idx] = inv[idx_l] + inv[idx_r] + min(opt_1, opt_2); sets[idx] = move(sets[idx_r]); } else { sets[idx].insert(x); } }; dfs(0, dfs); cout << inv[0] << "\n"; }
#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...