oj.uz

Submission #547637

# Submission time Handle Problem Language Result Execution time Memory
547637 2022-04-11T06:38:54 Z Jomnoi Tree Rotations (POI11_rot) C++17
63 / 100
 179 ms 29912 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]];
    }
    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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9732 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9776 KB Output is correct
2 Correct 5 ms 9732 KB Output is correct
3 Correct 5 ms 9756 KB Output is correct
4 Correct 5 ms 9732 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 6 ms 9836 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10332 KB Output is correct
2 Correct 8 ms 10068 KB Output is correct
3 Correct 7 ms 10452 KB Output is correct
4 Correct 8 ms 10452 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11860 KB Output is correct
2 Correct 14 ms 10900 KB Output is correct
3 Correct 33 ms 12748 KB Output is correct
4 Correct 12 ms 11668 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 14184 KB Output is correct
2 Correct 32 ms 15992 KB Output is correct
3 Correct 40 ms 18340 KB Output is correct
4 Correct 35 ms 18208 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 24960 KB Output is correct
2 Correct 50 ms 21896 KB Output is correct
3 Correct 69 ms 19468 KB Output is correct
4 Correct 45 ms 17544 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 18488 KB Output is correct
2 Correct 68 ms 21364 KB Output is correct
3 Incorrect 67 ms 26552 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 10.0

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