Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
2.3 kB
6
Indexable
Never
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

struct fenwick {

    int size;
    vector<int> tree;

    fenwick(int n) {
        size = n;
        tree.assign(size, 0);
    }

    int get(int r) {
        int res = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1) {
            res += tree[r];
        }
        return res;
    }

    int get(int l, int r) {
        return get(r) - get(l - 1);
    }

    void add(int x) {
        for (; x < size; x |= x + 1) {
            tree[x] += 1;
        }
    }

};

int n;
vector<pair<int, int>> balls;
vector<vector<int>> dp;
vector<vector<int>> invw, invb;

int solve(int i, int j) {
    if (dp[i][j] != -1) {
        return dp[i][j];
    }
    if (i == 0) {
        dp[i][j] = solve(i, j - 1) + invb[j][i + 1];
    } else if (j == 0) {
        dp[i][j] = solve(i - 1, j) + invw[i][j + 1];
    } else {
        dp[i][j] = min(solve(i - 1, j) + invw[i][j + 1], solve(i, j - 1) + invb[j][i + 1]);
    }
    return dp[i][j];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    dp.assign(n + 1, vector<int> (n + 1, -1));
    dp[0][0] = 0;
    invw.assign(n + 1, vector<int> (n + 2, 0));
    invb.assign(n + 1, vector<int> (n + 2, 0));
    int inv = 0;
    fenwick bl(n + 1), wh(n + 1);
    for (int i = 0; i < 2 * n; i++) {
        char t;
        int v;
        cin >> t >> v;
        if (t == 'W') {
            balls.emplace_back(v, 0);
            for (int j = 0; j < i; j++) {
                if (balls[j].second == 0 && balls[j].first > v) {
                    inv++;
                }
            }
            for (int j = 0; j <= n; j++) {
                invw[v][j] = bl.get(j, n);
            }
            wh.add(v);
        } else {
            balls.emplace_back(v, 1);
            for (int j = 0; j < i; j++) {
                if (balls[j].second == 1 && balls[j].first > v) {
                    inv++;
                }
            }
            for (int j = 0; j <= n; j++) {
                invb[v][j] = wh.get(j, n);
            }
            bl.add(v);
        }
    }
    cout << inv + solve(n, n);
    return 0;
}