断層 (Geologic Fault)
日本語
Language
Contribute a translation- Time limit
- 2000 ms
- Memory limit
- 256 MB
- Submissions
- 0
- Correct
- 0
- Solved by
- 0
- AC rate
- —
Statement
遠い昔，IOI 文明という高度な文明が栄えていた．しかし，火山の噴火により，この高度な文明はついに滅んでしまった．IOI 文明は直線状の河川に沿って繁栄しており，IOI 文明が滅んだとき，その地表面は平らであった．IOI 文明の跡地は座標平面の \(x\) 軸と見なすことができる．\(y\) 軸は高さ方向を表す．すなわち，座標平面において，直線 \(y = 0\) は地表を，領域 \(y > 0\) は地上を，領域 \(y < 0\) は地下を表す．また，IOI 文明が滅んだとき，\(a\) 年前 (\(a \geqq 0\)) の地層は，直線 \(y = -a\) の位置にあった．
IOI 文明が滅んだ後，IOI 文明の跡地では \(Q\) 回の地殻変動が起きた．\(i\) 回目 (\(1 \leqq i \leqq Q\)) の地殻変動は，位置 \(X_i\)，方向 \(D_i\)，変動の量 \(L_i\) で表される．\(D_i\) は \(1\) または \(2\) である．\(i\) 回目の地殻変動は以下のように起きる．
- 地層の移動が次のように起きる．
- \(D_i = 1\) のとき，断層が点 \((X_i, 0)\) を通る傾き \(1\) の直線に沿って造られ，この直線より上の領域にある地層が，直線に沿って高さ \(L_i\) だけ移動する．すなわち，この直線より上の点 \((x, y)\) は，点 \((x + L_i, y + L_i)\) に移動する．
- \(D_i = 2\) のとき，断層が点 \((X_i, 0)\) を通る傾き \(-1\) の直線に沿って造られ，この直線より上の領域にある地層が，直線に沿って高さ \(L_i\) だけ移動する．すなわち，この直線より上の点 \((x, y)\) は，点 \((x - L_i, y + L_i)\) に移動する．
- そのすぐ後に，領域 \(y > 0\) の地層が風化によってすべて消える．
時は変わり現代，考古学者の JOI 博士は IOI 文明の遺跡を発掘することにした．JOI 博士はどの位置の地表の地層が，IOI 文明が滅ぶ何年前の地層であるかを知りたい．どのような地殻変動が起きたかは分かっている．あなたの仕事は，JOI 博士にかわって，\(1 \leqq i \leqq N\) を満たす各整数 \(i\) について，点 \((i - 1, 0)\) と点 \((i, 0)\)の間の地表の地層が IOI 文明が滅ぶ何年前の地層であるかを求めることである．
課題
IOI 文明の跡地に起きたの情報が与えられたとき，すべての整数 \(i\) (\(1 \leqq i \leqq N\)) に対し，点 \((i - 1, 0)\) と点 \((i, 0)\) の間の地表の地層が IOI 文明が滅ぶ何年前の地層であるかを出力せよ．
Input
標準入力から以下の入力を読み込め．
- \(1\) 行目には，\(2\) 個の整数 \(N, Q\) が空白を区切りとして書かれている．これは，答えを求める地点の数が \(N\)，地殻変動の回数が \(Q\) であることを表す．
- 続く \(Q\) 行のうちの \(i\) 行目 (\(1 \leqq i \leqq Q\)) には，\(3\) 個の整数 \(X_i, D_i, L_i\) が空白を区切りとして書かれている．これは，\(i\) 回目の地殻変動の位置が \(X_i\)，方向が \(D_i\)，変動の量が \(L_i\) であることを表す．
Output
出力は \(N\) 行からなる．標準出力の \(i\) 行目 (\(1 \leqq i \leqq N\)) には，点 \((i - 1, 0)\) と点 \((i, 0)\) の間の地表の地層が IOI 文明が滅ぶ何年前の地層であるかを表す整数を出力せよ．
Constraints
すべての入力データは以下の条件を満たす．
- \(1 \leqq N \leqq 200\,000\)．
- \(1 \leqq Q \leqq 200\,000\)．
- \(-1\,000\,000\,000 \leqq X_i \leqq 1\,000\,000\,000\) (\(1 \leqq i \leqq Q\))．
- \(1 \leqq D_i \leqq 2\) (\(1 \leqq i \leqq Q\))．
- \(1 \leqq L_i \leqq 1\,000\,000\,000\) (\(1 \leqq i \leqq Q\))．
Subtasks
小課題 1 [18 点]
以下の条件を満たす．
- \(N \leqq 100\)．
- \(Q \leqq 100\)．
- \(-100 \leqq X_i \leqq 100\) (\(1 \leqq i \leqq Q\))．
- \(L_i = 1\) (\(1 \leqq i \leqq Q\))．
小課題 2 [16 点]
以下の条件を満たす．
- \(N \leqq 3,000\)．
- \(Q \leqq 3,000\)．
小課題 3 [66 点]
追加の制限はない．
Examples
10 2 12 1 3 2 2 2
3 3 5 5 5 5 5 5 2 2
この入力例は，以下の図に対応する．
10 6 14 1 1 17 1 1 -6 2 1 3 2 1 4 1 1 0 2 1
5 5 4 5 5 5 5 5 4 4
この入力例は，小課題 \(1\) の制約を満たす．
15 10 28 1 7 -24 2 1 1 1 1 8 1 1 6 2 1 20 1 3 12 2 2 -10 1 3 7 2 1 5 1 2
15 14 14 14 14 12 12 12 12 12 12 12 15 15 12
Notes
JOI 2016 · JCIOI · CC BY-SA 4.0
Tags
No tags yet