Submission #3012971

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define FORR(I,A,B) for(ll I = (B-1); I >= (A); --I)
const ll INF=1e18+7;
const ll MOD=1e9+7;

struct Inversions{// tentosu
	// after init,u can get number of inversions num_inverstion(A)
	vector<ll> L,R;
	void initsize(ll n){//input size of A
		L.resize(n/2+2);
		R.resize(n/2+2);
	}
	ll merge(vector<ll> &A,ll n,ll left,ll mid,ll right){
		ll i,j,k;
		ll cnt = 0;
		ll n1 = mid - left;
		ll n2 = right - mid;
		for(i=0;i<n1;i++)L[i]=A[left+i];
		for(i=0;i<n2;i++)R[i]=A[mid+i];
		L[n1]=R[n2]=INT_MAX;//
		i=j=0;
		for(k=left;k<right;k++){
			if(L[i]<=R[j]){
				A[k]=L[i++];
			}else{
				A[k]=R[j++];
				cnt += n1-i;
			}
		}
		return cnt;
	}
	ll mergeSort(vector<ll> &A,ll n,ll left,ll right){
		ll mid;
		ll v1,v2,v3;
		if(left+1<right){
			mid = (left+right)/2;
			v1 = mergeSort(A,n,left,mid);
			v2 = mergeSort(A,n,mid,right);
			v3 = merge(A,n,left,mid,right);
			return v1+v2+v3;
		}else return 0;
	}
	ll num_inverstion(vector<ll> A){
		vector<ll> B=A;//Aの順番を変えたくないなら
		return mergeSort(B,B.size(),0,B.size());
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n;
	cin>>n;
	vector<ll> ans(2*n);
	priority_queue<P> b,r;
	FOR(i,0,2*n){
		ll a;char c;
		cin>>c>>a;
		if(c=='B'){
			b.push({-a,i});
		}else{
			r.push({-a,i});
		}
	}
	FOR(i,0,2*n){
		if(b.size()>0&&r.size()>0){
			if(b.top().second<r.top().second){
				ans[b.top().second] = i;
				b.pop();
			}else{
				ans[r.top().second] = i;
				r.pop();
			}
		}else if(b.size()>0){
			ans[b.top().second] = i;
			b.pop();
		}else if(r.size()>0){
			ans[r.top().second] = i;
			r.pop();
		}
	}
	Inversions in;
	in.initsize(2LL*n);
	cout<<in.num_inverstion(ans)<<endl;
}

Submission Info

Judge Result