https://atcoder.jp/contests/abc128/tasks/abc128_e
解説
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); } }