oj.uz

Submission #547634

# Submission time Handle Problem Language Result Execution time Memory
547634 2022-04-11T06:33:31 Z Jomnoi Tree Rotations (POI11_rot) C++17
0 / 100
 180 ms 29988 KB 
#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]] + 1;
    }
    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, 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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 10324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 11884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 14136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 25044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 18456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 180 ms 29988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 133 ms 25428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 141 ms 25756 KB Output isn't correct
2 Halted 0 ms 0 KB -