oj.uz

답안 #1067031

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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