Codeforces #624 : Div3. F. Moving Points

途中の問題でハックされて全完ならず。
https://codeforces.com/contest/1311/problem/F

問題

１次元の数直線上で、N個の点が等速直線運動を行う。
d(i,j)を、２点i,jが最も近づくときの距離とする。

d(i,j)の総和を求めよ。

解法

点が衝突するときはd(i,j)は0だし、衝突しないときはd(i,j)は初期位置の距離となる。
よって、以下を数え上げればよい。

• ２点のうち初期状態で左側にいるほうが速度が速い場合、両者の初期位置の差

これは点を初期位置順及び速度順にソートして、BITを使い自身の左ないし右にいる頂点数を数え上げて行けば求められる。

int N;
pair<ll,ll> P[202020];
pair<ll,ll> Q[202020];
//さらに短縮
template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> bt,bt2;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i].first;
	FOR(i,N) cin>>P[i].second;
	sort(P,P+N);
	ll ret=0;
	FOR(i,N) Q[i]={P[i].second,i};
	
	sort(Q,Q+N);
	FOR(i,N) {
		ret+=bt(Q[i].second)*P[Q[i].second].first;
		bt.add(Q[i].second,1);
	}
	reverse(Q,Q+N);
	FOR(i,N) {
		ret-=(bt2(N)-bt2(Q[i].second))*P[Q[i].second].first;
		bt2.add(Q[i].second,1);
	}
	cout<<ret<<endl;
	
}

まとめ

このころはまだまだすんなり。