問題一覧 > 通常問題

No.855 ヘビの日光浴

レベル : / 実行時間制限 : 1ケース 3.153秒 / メモリ制限 : 315 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 12
作問者 : CuriousFairy315CuriousFairy315 / テスター : QCFiumQCFium
0 ProblemId : 2897 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-07-26 23:57:57

問題文

315国の中央にある山々には、大きさ$W$×$H$の長方形の形をした谷があることが知られています。
この谷には$2(W+H)$体のヘビが住み着いており、どのヘビも谷の壁面に巣穴を作って暮らしています。
ヘビは爬虫類なので、太陽が昇っている時間には日光浴をしようとします。
ですが、臆病なヘビは何かにぶつかると直ぐに巣穴に戻ってしまいます。
これから、$N$個のクエリが与えられます。
第$i$番目のクエリでは、$(X_i, Y_i)$の壁に巣穴を持つヘビが巣穴から体を$L_i$だけ前に出します。
ヘビの体の長さは十分に長く、巣穴から体が完全に出ることはありません。
また、ヘビ同士がぶつかった場合、即座に両ヘビは現在行っている移動を中止して巣穴に戻ってしまいます。
全てのクエリが終わったとき、各ヘビについて巣穴から体がどれだけ出ているかを求め、それを合計した値を出力してください。

補足(読まなくても大丈夫です)
全てのヘビは最初巣穴から体を出していないものとし、巣穴から体を出す時は必ず巣穴から見て谷がある方向に体を伸ばします。
全ての整数座標の壁にはヘビが丁度一匹のみ生息しており、巣穴にヘビが居なかったり複数体居ることはありません。
また、クエリは上から順に1個ずつ処理をするものとします。
挙動に関してはサンプルも見て確認してください。

入力

$H$ $W$ $N$
$X_1$ $Y_1$ $L_1$
$\vdots$
$X_N$ $Y_N$ $L_N$

$1 \leq W, H \leq 10^9$
$1 \leq N \leq 10^5$
$1 \leq L_i \leq 10^9$
$1\leq X_i \leq W$かつ$Y_i$が$0$か$H+1$、あるいは$1 \leq Y_i \leq H$かつ$X_i$が$0$か$W+1$
注: $(X_i, Y_i)$は$(0, Y_i)$, $(W+1, Y_i)$, $(X_i, 0)$, $(X_i, H+1)$のどれかであり、これは谷の外側となる(谷は$(1, 1)$から$(W, H)$の範囲である)

出力

各ヘビについて巣穴から伸ばしている体の長さの合計を出力せよ。
最後に改行すること。

サンプル

サンプル1
入力
3 5 4
2 0 2
4 4 3
0 2 3
0 2 1
出力
4

まず、1つめのクエリによって$(2, 0)$に住むヘビは体を$(2, 0)$から$(2, 2)$へ伸ばします。
次に、2つめのクエリによって$(4, 4)$に住むヘビは体を$(4, 4)$から$(4, 1)$へ伸ばします。
次に、3つめのクエリによって$(0, 2)$に住むヘビは体を$(0, 2)$から$(3, 2)$へ伸ばそうとしますが、途中の$(2, 2)$で最初のヘビとぶつかるため、両者体を巣穴に戻してしまいます。
最後に、4つめのクエリによって$(0, 2)$に住むヘビは体を$(0, 2)$から$(1, 2)$へ伸ばします。
よって、$(4, 4)$から$(4, 1)$へ体を伸ばしたヘビが長さ$3$であり、$(0, 2)$から$(1, 2)$へ体を伸ばしたヘビが長さ$1$なので、合計値である$4$を出力します。

サンプル2
入力
2 2 3
1 3 2
3 2 1
3 2 1
出力
0

既に体を巣穴から伸ばしているヘビが指定された場合、その体を更に伸ばします。
その結果として他のヘビとぶつかった場合はもちろん巣穴に戻ります。

サンプル3
入力
10 10 1
0 1 100
出力
0

他の巣穴まで体を伸ばした場合、その巣穴に住むヘビとぶつかるため巣穴に戻ります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。