Submission #3924134

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define FOR(i,m,n) for (ll i = m; i < n; ++i)

struct BIT {
  vector<ll> data;
  int N;

  BIT(int n) {
    N = n;
    data = vector<ll>(N+1);
  }

  void add(ll i, ll x) {
    for (ll k = i; k <= N; k += k&-k) data[k] += x;
  }

  void update(int i, ll x) {
    add(i, x-get(i));
  }

  ll sum(int i) {
    ll res = 0;
    for (int k = i; k > 0; k -= k&-k) res += data[k];
    return res;
  }

  ll get(int i) {
    return sum(i) - sum(i-1);
  }
};

const int MAX = 2019;
ll N;
string s;
int a;
ll dp[MAX][MAX]; //dp[i][j]:左から黒をi個、白をj個並べるためにかかった回数
int b[MAX], w[MAX], x[MAX*2];

int main() {

  cin >> N;
  REP (i, 2*N) {
    cin >> s >> a;
    if (s == "B") {
      x[i] = a;
      b[a] = i;
    } else {
      x[i] = a+N;
      w[a] = i;
    }
  }
  dp[0][0] = 0;

  BIT bitBlack(N*2);
  BIT bitWhite(N*2);
  FOR (i, 1, N+1) {
    bitBlack.add(b[i]+1, 1);
    dp[i][0] = dp[i-1][0] + b[i] - bitBlack.sum(b[i]+1) + 1;

    bitWhite.add(w[i]+1, 1);
    dp[0][i] = dp[0][i-1] + w[i] - bitWhite.sum(w[i]+1) + 1;
  }

  bitBlack = BIT(N*2);
  FOR (i, 1, N+1) {
    bitBlack.add(b[i]+1, 1);
    bitWhite = BIT(N*2);
    FOR (j, 1, N+1) {
      bitWhite.add(w[j]+1, 1);
      int new_b = dp[i-1][j] + b[i] - bitBlack.sum(b[i]+1) - bitWhite.sum(b[i]+1) + 1;
      int new_w = dp[i][j-1] + w[j] - bitBlack.sum(w[j]+1) - bitWhite.sum(w[j]+1) + 1;
      dp[i][j] = min(new_b, new_w);
    }
  }
  
  cout << dp[N][N] << endl;
}

Submission Info

Judge Result