ABC128 E - Roadwork (500)

E - Roadwork

概要

数直線上の座標0にQ人の人がいる。人iは時刻Diから数直線上正の向きに毎秒1ずつ進む。
数直線上ではN回の工事が行われており、工事iでは時刻Si-0.5から時刻Ti-0.5の間、座標Xiが通行止めである。
人iは最初に通行止めにあった時点で停止する。各人の停止位置を出力せよ。(停止しない場合は-1)

制約

1 ≦ N, Q ≦ 2 * 10^5
1 ≦ Si, Ti, Xi ≦ 10^9
0 ≦ Di ≦ 10^9

方針

時刻Dでスタートした人が工事iで停止する場合、Si ≦ D + Xi < Ti, すなわちSi - Xi ≦ D < Ti - Xi を満たす。また、複数の工事で停止する可能性がある場合、Xiがもっとも小さい工事場所で停止する。

上記を踏まえ、次のようなデータ構造を用いて問題を処理していく。
・イベント管理(vector v )
・工事中の座標管理(multiset ms)

vは工事開始、工事終了、人出発のそれぞれのイベントを時刻順に並べる。各イベントについて次のような処理をしてゆく。
工事開始：msに工事座標を追加
工事終了：msから工事座標を消去
人出発：その時間に出発した場合に停止する工事中の箇所のうち、もっとも小さい座標をmsから取得する

感想

最初は工事中の座標管理にpriority_queueも併用していたのですが、*ms.begin()で最小値を取得できるため、multisetだけで十分でした。
multisetはerase(要素)だと要素全部消えてerase(イテレータ)だとそのイテレータの場所だけ消えるのは重要です。これでちょっとバグりました。

解答

Submission #5657242 - AtCoder Beginner Contest 128

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
typedef tuple<ll, int, ll> tup;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll N, Q;
	cin >> N >> Q;
 
	vector<tup> v;
	rep(i, N){
		ll s, t, x;
		cin >> s >> t >> x;
		v.push_back((tup){2 * (s - x) - 1, 1, x});
		v.push_back((tup){2 * (t - x) - 1, 2, x});
	}
 
	rep(i, Q){
		ll d;
		cin >> d;
		v.push_back((tup){2 * d, 0, 0});
	}
 
	sort(v.begin(), v.end());
 
	// rep(i, v.size()){
	// 	cout << get<0>(v[i]) << "," << get<1>(v[i]) << "," << get<2>(v[i]) << endl;
	// }
	multiset<ll> ms;
 
	for(int i = 0; i < v.size(); i++){
		ll a = get<0>(v[i]);
		int b = get<1>(v[i]);
		ll x = get<2>(v[i]);
 
		if(b == 0){
			if(ms.empty()){
				cout << -1 << endl;
			}else{
				cout << *ms.begin() << endl;
			}
			continue;
		}
 
		if(b == 2){
			ms.erase(ms.find(x));
			continue;
		}
		ms.insert(x);
	}
}