Roadwork [AtCoder Beginner Contest 128 E]

https://atcoder.jp/contests/abc128/tasks/abc128_e

前提知識

• 遅延セグメントツリー（区間min代入、一点取得）

解説

https://atcoder.jp/contests/abc128/submissions/5778872

Q人の人はみな座標0からスタートして、速度1で歩くので、
ある地点Xiで[Si,Ti)だけ塞ぐ道路工事が塞ぐ人は、[Si-Xi,Ti-Xi)にスタートする人である。
よって、ある人が止まる地点は[Si-Xi,Ti-Xi)の区間でスタートする工事のうちX[i]が最小のもの。
これを高速に解くのは難しいが、setとかを使えばやれそう。
　
しかし、今回の問題は遅延セグメントツリーでもゴリ押せる。
データ構造をゴリゴリ使う場合は遅延セグメントツリーで区間代入min, 一点取得のデータ構造を作ってやればいい。
自分はたまたまそれを持ってたので、それを使って解く。
ある道路工事で足止めする可能性のある[Si-Xi,Ti-Xi)にスタートする人は、区間になる。
この区間にX[i]をmin代入する。
これを全ての道路工事で行えば、ある人について足止めされる区間が分かる。

int N, Q, S[201010], T[201010], X[201010], D[201010];
LazySegTree<int, 1 << 18> st;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> Q;
	rep(i, 0, N) cin >> S[i] >> T[i] >> X[i];
	rep(i, 0, Q) cin >> D[i];

	vector<int> queue;
	rep(i, 0, Q) queue.push_back(D[i]);

	rep(i, 0, N) {
		int L = S[i] - X[i];
		int R = T[i] - X[i];

		if (R <= 0) continue;

		chmax(L, 0);

		int a = lower_bound(all(queue), L) - queue.begin();
		int b = lower_bound(all(queue), R) - queue.begin();

		st.update(a, b, X[i]);
	}

	rep(q, 0, Q) {
		int ans = st.get(q, q + 1);
		if (ans == inf) ans = -1;
		printf("%d\n", ans);
	}
}