Submission #8399473

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
using ll     = long long;
using pii    = pair<int, int>;
using pll    = pair<ll, ll>;
using vi     = vector<int>;
using vl     = vector<ll>;
using vvi    = vector<vi>;
using vvl    = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

// Binary Indexed Tree / Fenwick tree
// can calculate partial sum in O(logN)
// can update single datum in O(logN)
// lower_bound is binary search O(logN)
// 0-indexed!!!
template <typename T = int>
struct BinaryIndexedTree {
    int n;
    vector<T> bit;
    BinaryIndexedTree(int n_, T init = 0) : n(n_), bit(n_ + 1, init) {}
    BinaryIndexedTree(vector<T> init) : n(init.size() + 1), bit(init.size() + 1) {
        for (int i = 1; i < init.size() + 1; ++i) {
            bit[i] = init[i - 1];
        }
    }
    T sum(int i) {
        i++;
        T s = bit[0];
        for (int x = i; x > 0; x -= (x & -x))
            s += bit[x];
        return s;
    }
    void add(int i, T a) {
        i++;
        if (i == 0)
            return;
        for (int x = i; x <= n; x += (x & -x))
            bit[x] += a;
    }
    int lower_bound(int w) {
        if (w <= 0)
            return 0;
        int x = 0, r = 1;
        while (r < n)
            r <<= 1;
        for (int k = r; k > 0; k >>= 1) {
            if (x + k <= n && bit[x + k] < w) {
                w -= bit[x + k];
                x += k;
            }
        }
        return x + 1;
    }
    int upper_bound(int w) {
        if (w < 0)
            return 0;
        int x = 0, r = 1;
        while (r < n)
            r <<= 1;
        for (int k = r; k > 0; k >>= 1) {
            if (x + k <= n && bit[x + k] <= w) {
                w -= bit[x + k];
                x += k;
            }
        }
        return x + 1;
    }
    T query(int l, int r) { return sum(r - 1) - sum(l - 1); }
};

int main() {
    int n;
    cin >> n;
    vector<string> c(2 * n);
    vector<int> a(2 * n);
    vector<pii> black, white;
    for (int i = 0; i < 2 * n; ++i) {
        cin >> c[i] >> a[i];
        if (c[i] == "W")
            white.emplace_back(a[i], i);
        else
            black.emplace_back(a[i], i);
    }
    sort(white.begin(), white.end());
    sort(black.begin(), black.end());
    BinaryIndexedTree<int> bitw(2 * n);
    vvl dp(n + 1, vl(n + 1, INF));
    dp[0][0] = 0;
    for (int i = 0; i <= n; ++i) {
        BinaryIndexedTree<int> bitb(2 * n);
        for (int j = 0; j <= n; ++j) {
            if (i != 0 && dp[i - 1][j] != INF)
                chmin(dp[i][j],
                      dp[i - 1][j] + bitw.query(white[i - 1].second, 2 * n) + bitb.query(white[i - 1].second, 2 * n));
            if (j != 0)
                bitb.add(black[j - 1].second, 1);
        }
        if (i != 0)
            bitw.add(white[i - 1].second, 1);
        BinaryIndexedTree<int> bitb2(2 * n);
        for (int j = 1; j <= n; ++j) {
            if (dp[i][j - 1] != INF)
                chmin(dp[i][j],
                      dp[i][j - 1] + bitw.query(black[j - 1].second, 2 * n) + bitb2.query(black[j - 1].second, 2 * n));
            bitb2.add(black[j - 1].second, 1);
        }
    }
    cout << dp[n][n] << "\n";
    return 0;
}

Submission Info

Judge Result