oj.uz

Submission #547618

# Submission time Handle Problem Language Result Execution time Memory
547618 2022-04-11T06:06:01 Z Jomnoi Tree Rotations (POI11_rot) C++17
36 / 100
 1000 ms 65536 KB 
#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];
ordered_set <int> arr[MAX_N];

int read_input() {
    int now;
    cin >> now;
    if(now == 0) {
        now = ++cnt;
        L[now] = read_input();
        R[now] = read_input();
    }
    else {
        now += n;
        L[now] = R[now] = -1;
    }
    return now;
}

long long dfs(int u) {
    if(L[u] == -1 and R[u] == -1) {
        arr[u].insert(u - n);
        return 0;
    }

    int v1 = L[u], v2 = R[u];
    long long res = dfs(v1) + dfs(v2);
    long long inv = 0, all = arr[v1].size() * arr[v2].size();
    if(arr[v1].size() < arr[v2].size()) {
        swap(v1, v2);
    }

    if(DEBUG) {
        cout << v1 << " : ";
        for(auto x : arr[v1]) {
            cout << x << ' ';
        }
        cout << endl;
        cout << v2 << " : ";
        for(auto x : arr[v2]) {
            cout << x << ' ';
        }
        cout << endl << endl;
    }

    for(auto x : arr[v2]) {
        inv += arr[v1].size() - arr[v1].order_of_key(x + 1);
    }
    inv = min(inv, all - inv);

    swap(arr[u], arr[v1]);
    for(auto x : arr[v2]) {
        arr[u].insert(x);
    }
    return res + inv;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    read_input();

    cout << endl;
    cout << dfs(1);
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 31572 KB Output is correct
2 Correct 24 ms 31572 KB Output is correct
3 Correct 24 ms 31540 KB Output is correct
4 Correct 25 ms 31628 KB Output is correct
5 Correct 25 ms 31572 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31572 KB Output is correct
2 Correct 25 ms 31652 KB Output is correct
3 Correct 27 ms 31636 KB Output is correct
4 Correct 26 ms 31652 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31720 KB Output is correct
2 Correct 26 ms 31828 KB Output is correct
3 Correct 27 ms 31852 KB Output is correct
4 Correct 33 ms 31772 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 32924 KB Output is correct
2 Correct 36 ms 32760 KB Output is correct
3 Correct 224 ms 32960 KB Output is correct
4 Correct 285 ms 33092 KB Output is correct

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 35392 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 50508 KB Output is correct
2 Execution timed out 1088 ms 38416 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 53208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 36996 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 190 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 39424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 38868 KB Time limit exceeded
2 Halted 0 ms 0 KB -