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;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using index_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int maxn = 500001;
index_set<int> T[maxn];
ll ans = 0LL;
int cur = 1;
void dfs(int s){
int x; cin >> x;
if(x == 0){
int u1 = ++cur;
dfs(u1);
int u2 = ++cur;
dfs(u2);
if(sz(T[u1]) < sz(T[u2])) T[u1].swap(T[u2]);
int m1 = 0, m2 = 0;
for(auto e: T[u2]){
int x = T[u1].order_of_key(e);
m1 += x;
m2 += sz(T[u1])-x;
}
ans += (ll)min(m1, m2);
for(auto e: T[u2]){
T[u1].insert(e);
}
T[u2].clear();
T[s].swap(T[u1]);
}
else{
T[s].insert(x);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
dfs(1);
cout << ans;
}
# | 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... |