Submission #547638

#	Time	Username	Problem	Language	Result	Execution time	Memory
547638		Jomnoi	Untitled (POI11_rot)	C++17	100 / 100	252 ms	37228 KiB

Main

#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;
 
const int MAX_N = 4e5 + 10;
 
int n, cnt;
int L[MAX_N], R[MAX_N];
int fenwick[MAX_N];
vector <int> arr[MAX_N];
int sz[MAX_N];
long long ans;
 
void update(const int &idx, const int &val) {
    for(int i = idx; i < MAX_N; i += (i & -i)) {
        fenwick[i] += val;
    }
}
 
int query(const int &idx) {
    int res = 0;
    for(int i = idx; i >= 1; i -= (i & -i)) {
        res += fenwick[i];
    }
    return res;
}
 
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]];
    }
    else {
        now += n;
        sz[now] = 1;
        L[now] = R[now] = -1;
    }
    return now;
}
 
void dfs(const int &u, const bool &keep) {
    if(L[u] == -1 and R[u] == -1) {
        arr[u].push_back(u - n);
        update(u - n, 1);
    }
    else {
        int v1 = L[u], v2 = R[u];
        if(sz[v1] < sz[v2]) {
            swap(v1, v2);
        }
 
        dfs(v2, false);
        dfs(v1, true);
        
        long long inv = 0;
        for(auto x : arr[v2]) {
            inv += query(MAX_N - 1) - query(x);
        }
 
        swap(arr[u], arr[v1]);
        for(auto x : arr[v2]) {
            arr[u].push_back(x);
            update(x, 1);
        }
        ans += min(inv, 1ll*sz[v1] * sz[v2] - inv);
    }
 
    if(keep == false) {
        for(auto x : arr[u]) {
            update(x, -1);
        }
    }
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
 
    cin >> n;
    read_input();
 
    dfs(1, false);
    cout << ans;
    return 0;
}

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