Codeforces Round #502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2)

HIR180 @HIR180

普通に眠いので寝たい (F解いたら寝るか)

アルハンブラ宮殿のゆるキャラ @nebukuro09

めしくお

olphe @_olphe

うんらてｄ

1 @komori3_

C 通したので撤退　unrated は悲しい

agw @masashinakata

ギョエエエエエエ 　　　　　　　　こ ﾉ 　ふぉ 　　　　　　　　ﾉ　ど ノ 　　　　　　　ﾉ　 ﾉ 　〆 ⌒ヽ∩　ﾌﾞﾁﾌﾞﾁ 　(　 ﾟωﾟ)☆⌒ ミ 　ヽ⊂彡(´･ω･`)

agw @masashinakata

まあいいや。嫁はんと朝食たのしーしよう

~ @kosakkun

こどふぉで英語の謝罪文の勉強が出来る.

agw @masashinakata

unratedで支払われなかった賞金を積み立ててって、歳末に豪華なコンテスト開けばいんじゃないか? 賞金コンでunratedしたときの風向きも変わるぞ(?)

satanic@研究💪 @satanic0258

ん，なんか伸びてるような

有為 @uwitenpen

G実装おわんね・・

有為 @uwitenpen

あっ延長されてる

satanic@研究💪 @satanic0258

えー

satanic@研究💪 @satanic0258

こどふぉおつでした

有為 @uwitenpen

結局バグ取れなかったし・・

有為 @uwitenpen

Gは、最初すべての点に-∞を割り当てておいて、クエリ1で-∞→0またはk→k+1して、クエリ2で部分木内の値を-∞にし、クエリ3でルートまでのパスで、prefix sum >= whole sum になるのが1個でもあればOKみたいなのになったけど実装が重かった

kmjp @kmjp_pc

Eって凸包を並行移動と回転で重ねるだけの問題じゃないの…？問題文がいまいち理解できてない。

有為 @uwitenpen

@kmjp_pc だと思う

有為 @uwitenpen

凸包の同型判定、Z-algorithmで辺の長さ列完全一致したやつだけ試したけど、これをすさまじく裏切れるケースあるのかな・・

kmjp @kmjp_pc

@uwitenpen やっぱりそうですよね…。

有為 @uwitenpen

Fは篩うところを区間篩にしただけなんだけど・・

kmjp @kmjp_pc

Eは凸包求めて重心を原点に持って行って、原点からの距離が近そうな２点について回転角を求めて全点チェック、とかやったけどpretest通らなかった。

kmjp @kmjp_pc

Fはサイズ√N程度の篩にしてみたけど重くて5sギリギリだった。どうやったら1sとかで通るんだろう。vectorで素因数一覧持つのが悪かったのかな。

有為 @uwitenpen

区間篩の区間自体は√nに拘る必要はなくでかくとれる

有為 @uwitenpen

けどあまり関係ないか？

satanic@研究💪 @satanic0258

こどふぉ A:(合計,-ID)で降順ソート B:各bit位置でaがx,bがyのときの個数をc[xy]に足すとして,c[00]*c[10]+c[00]*c[11]+c[01]*c[10] C:元の順列を√n個のブロックで区切って逆順に並べる D:c[i][j]:=ペア(i,j)に対するWu値,とd[i][j]:=入力iに対してWu値がjになる個数,を前計算しておけば各クエリO(1)