This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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(2 * n + 1);
map<int, Tree<int>> sets;
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);
}
inv[idx] = inv[idx_l] + inv[idx_r] + min(opt_1, opt_2);
sets[idx].swap(sets[idx_r]);
sets.erase(idx_l);
sets.erase(idx_r);
} else {
sets[idx].insert(x);
}
};
dfs(0, dfs);
cout << inv[0] << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |