Submission #1067025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067025		vux2code	Untitled (POI11_rot)	C++17	100 / 100	97 ms	19292 KiB

Main

// 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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 10 / 10