Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 245 E問題 Wrapping Chocolate

AtCoder ABC ABC245 E問題 500 pts

問題

提出解答

問題の概要

長さ $N$ の非負整数列 $A=(A_i)_{i=1}^N, B=(B_i)_{i=1}^N$ と長さ $M$ の非負整数列 $C=(C_j)_{j=1}^M, D=(D_j)_{j=1}^N$ が与えられる.

次を満たす長さ $N$ の列 $J=(J_i)_{i=1}^N$ は存在するか?

$1 \leq J_i \leq N$
$J_1, \dots, J_N$ は全て異なる.
$A_i \leq C_{J_i}, B_i \leq D_{J_i}$

制約

$1 \leq N \leq M \leq 2 \times 10^5$
$1 \leq A_i, B_i, C_j, D_j \leq 10^9$

解法

次のアルゴリズムにより, 正解できる.

$S$ を空集合とする.
$E:=\{A_1, \dots, A_N, C_1, \dots, C_M\}$ とする.
の要素のうち, 大きい順に以下を行う.
- $C_j=x$ となる全ての $j$ に対して, $S$ に $D_j$ を加える.
- $A_i=x$ となる全ての $i$ に対して, $S$ の要素の $B_i$ 以上であるもののうち, 最小の要素を削除する. 存在しない場合, 否定的結論.
ここまでくれば肯定的結論.

このアルゴリズムにおける $S$ の管理方法として, multiset や BIT を用いる事により, 時間計算量 $O((N+M) \log (N+M)$ で求める事ができる.