Submission #1067025

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1067025	2024-08-20T09:52:11 Z	vux2code	Tree Rotations (POI11_rot)	C++17	100 / 100	97 ms	19292 KB

// Src : Vux2Code
#include <bits/stdc++.h>
using namespace std;

const int mxn = 4e5 + 5;

int tin[mxn], tout[mxn], l[mxn], r[mxn], pos[mxn], fwk[mxn];
long long sz[mxn], dp[mxn];
int cnt = 0, n, t = 0;

void upd(int p, int val) {
    for (int i = p; i <= n; i += (i & -i)) {
        fwk[i] += val;
    }
}

int qry(int p) {
    int sum = 0;
    for (int i = p; i > 0; i -= (i & -i)) {
        sum += fwk[i];
    }
    return sum;
}

int input() {
    int cur;
    cin >> cur;
    if (cur == 0) {
        cur = ++cnt;
        l[cur] = input();
        r[cur] = input();
        tin[cur] = tin[l[cur]];
        tout[cur] = tout[r[cur]];
        sz[cur] = sz[l[cur]] + sz[r[cur]];
    } else {
        tin[cur] = tout[cur] = ++t;
        pos[t] = cur;
        sz[cur]++;
    }
    return cur;
}

void solve(int cur, bool keep) {
    if (cur <= n) {
        if (keep) {
            upd(pos[tin[cur]], 1);
        }
        return;
    }

    if (sz[l[cur]] < sz[r[cur]]) {
        swap(l[cur], r[cur]);
    }

    solve(r[cur], false);
    solve(l[cur], true);

    long long invcnt = 0;
    for (int i = tin[r[cur]]; i <= tout[r[cur]]; i++) {
        invcnt += qry(pos[i]);
    }

    dp[cur] = dp[l[cur]] + dp[r[cur]] + min(invcnt, (sz[l[cur]] * sz[r[cur]]) - invcnt);

    if (keep) {
        for (int i = tin[r[cur]]; i <= tout[r[cur]]; i++) {
            upd(pos[i], 1);
        }
    } else {
        for (int i = tin[l[cur]]; i <= tout[l[cur]]; i++) {
            upd(pos[i], -1);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    cnt = n;
    input();
    solve(n + 1, true);
    cout << dp[n + 1];

    return 0;
}

Subtask #1
9.0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	456 KB	Output is correct
5	Correct	348 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	860 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	860 KB	Output is correct
4	Correct	1 ms	860 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1624 KB	Output is correct
2	Correct	4 ms	1112 KB	Output is correct
3	Correct	12 ms	2160 KB	Output is correct
4	Correct	4 ms	1628 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	3164 KB	Output is correct
2	Correct	12 ms	4564 KB	Output is correct
3	Correct	16 ms	5720 KB	Output is correct
4	Correct	15 ms	5892 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	9780 KB	Output is correct
2	Correct	20 ms	8260 KB	Output is correct
3	Correct	24 ms	6780 KB	Output is correct
4	Correct	23 ms	6228 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	7252 KB	Output is correct
2	Correct	29 ms	8788 KB	Output is correct
3	Correct	29 ms	11612 KB	Output is correct
4	Correct	29 ms	11404 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	68 ms	12372 KB	Output is correct
2	Correct	48 ms	12636 KB	Output is correct
3	Correct	49 ms	12788 KB	Output is correct
4	Correct	51 ms	12368 KB	Output is correct
5	Correct	72 ms	10984 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	11856 KB	Output is correct
2	Correct	53 ms	18000 KB	Output is correct
3	Correct	61 ms	16208 KB	Output is correct
4	Correct	47 ms	18768 KB	Output is correct
5	Correct	97 ms	12716 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	12120 KB	Output is correct
2	Correct	52 ms	14668 KB	Output is correct
3	Correct	82 ms	13012 KB	Output is correct
4	Correct	59 ms	13652 KB	Output is correct
5	Correct	49 ms	19292 KB	Output is correct
6	Correct	94 ms	12884 KB	Output is correct

Submission #1067025

Compilation message