oj.uz

답안 #547638

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
547638 2022-04-11T06:39:22 Z Jomnoi Tree Rotations (POI11_rot) C++17
100 / 100
 252 ms 37228 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, 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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9704 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 7 ms 9812 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 10324 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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 11860 KB Output is correct
2 Correct 16 ms 10800 KB Output is correct
3 Correct 33 ms 12416 KB Output is correct
4 Correct 13 ms 11604 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 14220 KB Output is correct
2 Correct 36 ms 15796 KB Output is correct
3 Correct 38 ms 17876 KB Output is correct
4 Correct 42 ms 17808 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 24972 KB Output is correct
2 Correct 46 ms 21244 KB Output is correct
3 Correct 60 ms 18836 KB Output is correct
4 Correct 46 ms 16848 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 18428 KB Output is correct
2 Correct 66 ms 20400 KB Output is correct
3 Correct 74 ms 25648 KB Output is correct
4 Correct 64 ms 26052 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 29908 KB Output is correct
2 Correct 116 ms 27360 KB Output is correct
3 Correct 116 ms 26904 KB Output is correct
4 Correct 118 ms 26720 KB Output is correct
5 Correct 183 ms 27344 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 25412 KB Output is correct
2 Correct 129 ms 36084 KB Output is correct
3 Correct 156 ms 33028 KB Output is correct
4 Correct 97 ms 37228 KB Output is correct
5 Correct 236 ms 30324 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 25804 KB Output is correct
2 Correct 127 ms 28324 KB Output is correct
3 Correct 185 ms 28208 KB Output is correct
4 Correct 173 ms 27520 KB Output is correct
5 Correct 120 ms 36820 KB Output is correct
6 Correct 252 ms 30916 KB Output is correct