Submission #547638

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

Submission #547638

Compilation message