Submission #1067031

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1067031	2024-08-20T09:55:21 Z	vux2code	Tree Rotations (POI11_rot)	C++17	100 / 100	117 ms	22612 KB

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

template <typename T> void vout(T s){ cout << s << endl; exit(0);}
 
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;

// ll t = 1;

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);
        }
    }
}

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

int main () {
    ios::sync_with_stdio (0);
    cin. tie (0);
    cout. tie (0);
    // #define TASK "task"
    // freopen (TASK".inp", "r", stdin);
    // freopen (TASK".out", "w", stdout);
    // cin >> t;
    // while (t --) solve ();
    solve ();
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	12632 KB	Output is correct
2	Correct	2 ms	12636 KB	Output is correct
3	Correct	2 ms	12892 KB	Output is correct
4	Correct	2 ms	12636 KB	Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	12892 KB	Output is correct
2	Correct	2 ms	12636 KB	Output is correct
3	Correct	2 ms	12888 KB	Output is correct
4	Correct	2 ms	12892 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	13556 KB	Output is correct
2	Correct	6 ms	14680 KB	Output is correct
3	Correct	11 ms	12892 KB	Output is correct
4	Correct	4 ms	15448 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	10992 KB	Output is correct
2	Correct	12 ms	16148 KB	Output is correct
3	Correct	16 ms	15704 KB	Output is correct
4	Correct	16 ms	13660 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	19544 KB	Output is correct
2	Correct	20 ms	16988 KB	Output is correct
3	Correct	25 ms	16716 KB	Output is correct
4	Correct	19 ms	14216 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	14428 KB	Output is correct
2	Correct	27 ms	15708 KB	Output is correct
3	Correct	26 ms	18780 KB	Output is correct
4	Correct	26 ms	19816 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	17632 KB	Output is correct
2	Correct	51 ms	16208 KB	Output is correct
3	Correct	63 ms	16724 KB	Output is correct
4	Correct	49 ms	17012 KB	Output is correct
5	Correct	77 ms	14420 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	15964 KB	Output is correct
2	Correct	56 ms	22612 KB	Output is correct
3	Correct	58 ms	19308 KB	Output is correct
4	Correct	47 ms	22352 KB	Output is correct
5	Correct	90 ms	14420 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	15452 KB	Output is correct
2	Correct	76 ms	16444 KB	Output is correct
3	Correct	85 ms	14416 KB	Output is correct
4	Correct	61 ms	15364 KB	Output is correct
5	Correct	60 ms	22268 KB	Output is correct
6	Correct	117 ms	14420 KB	Output is correct

Submission #1067031

Compilation message