NOI 2019 Finals - Pilot
概要
問題へのリンク
Author : Cyanmond
解法
一番左と一番右に、番兵として高さ無限の山を考えると議論や実装が楽になる。これを山$ 0, N + 1とする。
飛行機$ jに関する答えは、$ H_i > Y_jであるような index$ i \ (0 \leq i \leq N + 1)を小さい方から順に$ W_1, W_2, \cdots ,W_xとしたとき$ \displaystyle \sum_{k=1}^{x-1} \frac{(W_{k + 1} - W_k) \times (W_{k + 1} - W_k + 1)}{2}である。
これをそのまま実装すれば$ O(N^2)でこの問題を解くことができる。$ H, Yをイベントソートして std::set などを用いることで、簡単に$ O(N \log N)時間が達成できる。
Cartesian Tree の構築のようにすると、$ \max (H, Y) = Xとして計算量$ O(N + X)が達成できる。この問題の制約下で$ X \leq 10^6である。また、座標圧縮を用いると$ O(N \log N)になるが、前の解法よりも恐らく定数倍が軽い。