Codeforces Round #560 (Div. 3)F2. Microtransactions (hard version)

問題概要

$n$ 個の商品があり, 各商品の値段は基本 $2$ 円である. 長さ $n$ の数列 $k$ が与えられ, これは $i$ 番目の商品を $k_i$ 個だけ購入する必要があることを示している.

上記とは別に, $m$ 個のセール情報 $d, t$ が与えられる. $j$ 番目のセール情報は, $d_j$ 日目に $t_j$ 番目の商品が $1$ 円で購入できることを示している.

$1$ 日の始まりに $1$ 円だけ入手することができる. 1日に何個でも商品を購入できるとき, $k$ の条件をすべて満たすには最低何日かかるか？

問題へのリンク

制約

$1 \le n, m \le 2\times 10^5$
$0 \le k_i \le 2\times 10^5$
$k_i$ の総和は $1$ 以上 $2\times 10^5$ 以下
$1\le d_j \le 2\times 10^5, 1 \le t_j \le n$

解法

明らかに二分探索です. $T$ 日で条件を満たせるか？という判定問題を考えましょう.

各商品のセールのうち, その商品の一番最後のセールで商品を買い, それより前のセールでは商品を買わないのが最適です(後にまわすことによるデメリットがありません). よって, 全ての商品につき一番最後のセールで買えるだけ買うのを繰り返し, 最終日に残金で帳尻合わせをします. ここで条件を満たせるなら Yes, 満たせないなら No をすればいいです.

実装

Submission #147408396 - Codeforces