Submission #2501794

---

Source Code Expand

#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,NAME,...) NAME
#define pr(...) GET_MACRO(__VA_ARGS__,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)
#define Pr(a) (#a)<<"="<<(a)<<" "
#define pr1(a) cerr<<Pr(a)<<endl;
#define pr2(a,b) cerr<<Pr(a)<<Pr(b)<<endl;
#define pr3(a,b,c) cerr<<Pr(a)<<Pr(b)<<Pr(c)<<endl;
#define pr4(a,b,c,d) cerr<<Pr(a)<<Pr(b)<<Pr(c)<<Pr(d)<<endl;
#define pr5(a,b,c,d,e) cerr<<Pr(a)<<Pr(b)<<Pr(c)<<Pr(d)<<Pr(e)<<endl;
#define pr6(a,b,c,d,e,f) cerr<<Pr(a)<<Pr(b)<<Pr(c)<<Pr(d)<<Pr(e)<<Pr(f)<<endl;
#define int long long
#define double long double
using namespace std;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
typedef pair<int,int> P;
typedef long long ll;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}

class RMQ{
public : 
  typedef long long ll;
  ll INF = 1LL<<55;
  struct data{
    bool type; //0 - empty   , 1 - update
    ll value;
  };
  ll n,n_;
  vector<ll> dat;
  vector<data> td;
  int toMax; //0 -> RangeMin 1->RangeMax;
  
  RMQ(){n=-1;}
  RMQ(int n_,int toMax = 0):n_(n_),toMax(toMax){
    n=1;
    while(n<n_)n*=2;
    td.resize(2*n-1,(data){0,0});
    dat.resize(2*n-1,INF);
  }
  
  //[a,b)の値をxに変更　update(a,b,x)
  ll update(int a,int b,ll x,bool flg=true,int k=0,int l=0,int r=-1){
    if(r == -1) {
      r = n;
      assert(a <= b), assert(a <= n && b <= n), assert(a >= 0 && b >= 0);
      if(toMax) x *= -1;
    }
    
    if(r<=a||b<=l)return flg? dat[k]:INF;
    if(a<=l&&r<=b){
      if(flg==true){
        td[k]=(data){1,x};
        dat[k]=x;
      }
      return dat[k];
    }
    
    if(td[k].type){
      td[k].type=0;
      dat[k*2+1] = dat[k*2+2] = td[k].value;
      td[k*2+1] = td[k*2+2] = (data){1,td[k].value};
    }
    
    ll vl=update(a,b,x,flg,k*2+1,l,(l+r)/2);
    ll vr=update(a,b,x,flg,k*2+2,(l+r)/2,r);
    if(flg==true)dat[k]=min(vl,vr);
    return min(vl,vr);
  }
  
  //[a,b)の最小値を得る　find(a,b);
  ll find(int a,int b){return (toMax? -1:1) * update(a,b,0,false);};
};


class RSAQ{
public:
  typedef long long ll;
  ll n;
  vector<ll> dat,td;
  
  RSAQ(){n = -1;}
  RSAQ(int n_){
    n=1;
    while(n<n_)n*=2; //要素数nを2のべき乗に
    dat.resize(2*n-1,0),td.resize(2*n-1,0);
  }
  
  //[a,b)の区間にxを加算する,query(a,b,x);
  ll add(int a,int b,ll x,int k=0,int l=0,int r=-1){
    if(r==-1) r=n, assert(a <= n && b <= n);
    if(r<=a||b<=l)return 0;
    if(a<=l&&r<=b){
      dat[k]+=(r-l)*x; 
      td[k]+=x;
      return dat[k];
    }

    dat[k]+=(min(r,b)-max(l,a))*x;
    ll kl=k*2+1,kr=k*2+2,t=td[k]*(r-l)/2;
    dat[kl]+=t, dat[kr]+=t;
    td[kl]+=td[k], td[kr]+=td[k];
    td[k]=0;

    ll vl=add(a,b,x,k*2+1,l,(l+r)/2);
    ll vr=add(a,b,x,k*2+2,(l+r)/2,r);
    return vl+vr;
  }
  
  //[a,b)の総和を得る
  ll sum(int a,int b){return add(a,b,0);}
};

const int N = 2001;
int n;
vector<P> W,B;
int used[N][N],mem[N][N];
int dfs(int i,int j, RSAQ &A){
  //pr(i, j);
  if(i == n && j == n) return 0;
  if(used[i][j]++) return mem[i][j];
  int a = INF, b = INF;
  
    if(i != n) {
      int idx = W[i].second;
      int cost = A.sum(0, idx);
      A.add(idx, idx+1, -1);
      a = cost + dfs(i+1,j, A);
      A.add(idx, idx+1, 1);
    }
    
    if(j != n){
      int idx = B[j].second;
      int cost = A.sum(0, idx);
      A.add(idx, idx+1, -1);
      b = cost + dfs(i, j+1, A);
      A.add(idx, idx+1, 1);
    }
    int res = min(a, b);
    return mem[i][j] = res;
}

signed main(){
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);
  cin>>n;
  

  for(int i=0;i<2 * n;i++){
    char ch;
    int val;
    int idx = i;
    cin>>ch>>val;
    if(ch == 'W') W.push_back(P(val,idx));
    else B.push_back(P(val,idx));
  }
  
  sort(W.begin(),W.end());
  sort(B.begin(),B.end());

  RSAQ A(2 * n);
  A.add(0 , 2*n , 1);

  int ans = dfs(0, 0, A);
  cout<<ans<<endl;
    
  return 0;
}

Submission Info

Judge Result