Codeforces Round #367 (Div. 2)

最後の問題が解けなかったのは残念。

hypot(x[i]-a, y[i]-b)/v[i] の最小値を求めればいい。出力桁数や min の初期値ミスに注意。

m[i] 以下の要素の個数が求めたい。これは累積和や二分探索（upper_bound）が使える。

累積和を使う場合は m[i] が 10⁹ なので配列外参照に注意。

ありうるミスとしては次のようなものだろうか。

c[i]≦10⁹ なので 10⁹*10⁵ より大きい値を INF を設定しておくとよい。

上位ビットになるべく 1 が立つようにすれば、それが最大値になる。たとえば x=10010 だったら、y=1**** よりは y=0**** と xor を取った方が大きくなる。

上から順にビットを決めていこうとすると、接頭辞が P であるようなものの存在を判定したくなる。これは trie を使って O(Q log x) でできる。

連結リストを使って行列を管理すると O((n+m)q) で解ける。連結リストに左・右・下のリンクを持たせればいい。

(a,b),(a,b+w),(c,d),(c,d+w) のノードを一回求めれば、その下のノードは下へのリンクを辿って取得できるため O(h+w) で横方向のリンクは張り替えられる。

横方向だけでなく縦方向のリンクも張り替える必要がある。a-1,c-1,a+H-1,b+H-1 行目以外のリンクは変化しないので O(w) で張り替えられる。

原理は簡単だが実装がやや面倒。

最近ジャッジが重すぎる気がする。