スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Codeforces Round #167 (Div. 1) A : Dima and Staircase

n 段の階段があり、左から i 番目の段は幅 1 で高さ a_i。

m 個の長方形のブロックを順番に落としていく。
i 番目のブロックは幅 w_i で高さ h_i。ブロックの左端が階段の左端に合うように垂直に落とす。
階段かすでに置かれているブロックと水平方向に接した時点で落下は止まる。

それぞれの長方形が床からどれだけの高さにあるかを求めよ。

・ 1 ≦ n, m ≦ 10^5
・ 1 ≦ a_i ≦ 10^9
・ a_i ≦ a_{i+1}
・ 1 ≦ w_i ≦ n
・ 1 ≦ h_i ≦ 10^9

解答

素直に考えると、各 x 座標における高さが管理できればよく、これを実現するには
・ y[i] = max( y[i], y_new ) ( i = L, L+1, ..., R )
・ find max{ y[L], y[L+1], ..., y[R] }
という二つのクエリを備えた segment tree を使えばよい。

遅延伝播は多分必要になる。

でも A 問題からそんなものが要求されるわけがないので、冷静に考えてみると、直前においたブロックの高さだけ覚えておけば計算はうまく回ることに気付く。
( ブロックの左端が同じ x 座標なので、各ブロックは階段か直前に置いたブロックにぶつかって止まる。)

ので、結局 O(n+m) とかで解ける。

ソースコード

O(n + m)
http://www.codeforces.com/contest/273/submission/3114403

O(n + m log n) (segment tree)
http://www.codeforces.com/contest/272/submission/3130273
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。