K-th Number (Segment Tree)

c++ SPOJ

SPOJ.com - Problem MKTHNUM 2104 -- K-th Number segment tree による手法だと一発で AC した。(SPOJ) メモリをたくさん使う分やはり速い。 merge は std::back_inserter を使ってもよいが事前に resize しておくほうが速いはず。バケット法はこちらK-th N…

2015-08-06

K-th Number

SPOJ c++

SPOJ.com - Problem MKTHNUM 2104 -- K-th Number 最近 yukicoder で平方分割をやったんで(No.96 圏外です。 - shifth’s blog)蟻本にのっていた問題を復習してみた。定数倍がきびしすぎるのか vector をやめて global 配列にして、 cin/cout を scanf/print…

2015-08-05

Largest Rectangle in Histgram

c++ SPOJ

SPOJ.com - Problem HISTOGRA せっかくなんでブログの過去記事からひっぱってきた。スタックにつむときに 2 パターンあるのがポイント class largest_rectangle_in_histogram { public: // 長方形の始点と終点を回る、素朴な2重ループでは O(N^2) で TLE し…