Hatena::Grouptopcoder

Hiro180の日記

 | 

2014-03-02

UTPC 2013 I 18:04

※たぶん想定解法ではないです


dfsして適当に並べると2次元平面状で「自分より左下にある数字のうち最も近いもの」を求める、という問題を

2回解けばよくなるので、multisetを乗せたsegtreeを作ったらTLEしました。

でも飛んでくるクエリが必ず0~hogeであることからBITに変更したら通った。

一応O(N log^2 N)です。上から降りてくと簡単に解けるかもしれませんが分かりません。

 |