Solved today - ICPC突破専用ザク

部内の勉強会でやった．

よく見たらもう過去に解いてたりするんだけど普通に忘れていたし，また書いた．O(N^3)じゃないと駄目だと思っていたんですがテストケースが弱いのかO(N^4)でも普通に通るみたいです．ワオ．

6x6のマス目に1x1,2x2,...,6x6の正方形を詰める．
大きいものから入れていく方針でひたすら場合分けしていく．実装は美しくならないと思う．刺身タンポポゲー．

左端座標でソートしてやって，もっとも右端が大きいものから順に覆っていってやる．
番兵として{M+1,M+1}みたいな板を追加しておくとやりやすいかも?

実装ゲー．実装力が問われる．
N<=2*10^9程度なので，列を群数列で分けた場合高々10000群くらいまでしかいかないので，第1群，第2群，…から順みて，どの群にいるのかが分かれば求まる．
実装はstringstreamで数字をじゃんじゃか流していくと割と楽にできると思う．

上のビットから決定していく．bビット目を0にできるか|1にできるかというフラグを保持させ，Nのbビット目が0なら1にさせる方向に，bビット目が1なら0にさせる方向に促す．
bビット目の値を決定したらそれに応じてU,Lを変化させてやって，U,Lのbビット目以上は一致している状態を保ってやるとよい．