yukicoder : No.1012 荷物収集

これはまぁ定番テクかな…。
https://yukicoder.me/problems/no/1012

問題

数直線上にN個の荷物があり、各座標と重さが与えられる。
荷物を距離1動かすには重さと等しいコストがかかる。
指定された地点に荷物を集めるコストを答えよ。

解法

以下Editorialのtester解相当の解法。

重さW荷物の右側にいるとき、左に1動けばコストがW下がるし右に動けばW上がる。
左側にいるときはその逆。

そこで、自分の位置の左側にある重さの総量と右側にある重さの総量を考えながら、クエリと荷物の位置を合わせてX座標順に走査しよう。
X座標を1動かすごとに、左右の荷物の重さの総和に応じてコストが一定量増減する。
荷物を通り過ぎると、左と右の重さが変わる。

int N,Q;
int X[101010],W[101010];
int Y[101010];
ll ret[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	ll L=0,R=0;
	ll sum=0;
	vector<pair<int,int>> ev;
	FOR(i,N) {
		cin>>X[i]>>W[i];
		sum+=1LL*X[i]*W[i];
		R+=W[i];
		ev.push_back({X[i],i});
	}
	FOR(i,Q) {
		cin>>Y[i];
		ev.push_back({Y[i],i+N});
	}
	int cur=0;
	sort(ALL(ev));
	FORR(e,ev) {
		ll dx=e.first-cur;
		sum+=L*dx;
		sum-=R*dx;
		cur=e.first;
		
		x=e.second;
		if(x<N) L+=W[x],R-=W[x];
		else ret[x-N]=sum;
		
	}
	FOR(i,Q) cout<<ret[i]<<endl;
	
}

まとめ

時間通り参加したかった。