Submission #547636

#	Time	Username	Problem	Language	Result	Execution time	Memory
547636		Jomnoi	Untitled (POI11_rot)	C++17	0 / 100	1101 ms	65536 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define DEBUG 0
using namespace std;
using namespace __gnu_pbds;
 
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
 
const int MAX_N = 4e5 + 10;
 
int n, cnt;
int L[MAX_N], R[MAX_N], sz[MAX_N];
ordered_set <int> arr[MAX_N];
long long ans;

int read_input() {
    int now;
    cin >> now;
    if(now == 0) {
        now = ++cnt;
        L[now] = read_input();
        R[now] = read_input();
        sz[now] = sz[L[now]] + sz[R[now]] + 1;
    }
    else {
        now += n;
        sz[now] = 1;
        L[now] = R[now] = -1;
    }
    return now;
}
 
void dfs(const int &u) {
    if(L[u] == -1 and R[u] == -1) {
        arr[u].insert(u - n);
        return;
    }
 
    int v1 = L[u], v2 = R[u];
    dfs(v1);
    dfs(v2);
    if(arr[v1].size() < arr[v2].size()) {
        swap(v1, v2);
    }
 
    long long inv = 0;
    for(auto x : arr[v2]) {
        inv += arr[v1].size() - arr[v1].order_of_key(x + 1);
    }
    ans += min(inv, sz[v1] * sz[v2] - inv);
 
    swap(arr[u], arr[v1]);
    for(auto x : arr[v2]) {
        arr[u].insert(x);
    }
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
 
    cin >> n;
    read_input();
 
    dfs(1);
    cout << ans;
    return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 10