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