Skip to content
Sign in

フェーン現象 (Foehn Phenomena)

Unrated
日本語

Language

Contribute a translation
Time limit
1000 ms
Memory limit
256 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

IOI 国では海から陸に向かって常に風が吹いている．風は地点 \(0\) から地点 \(1\)，地点 \(2\)，\(\ldots\) という経路を通りながら地点 \(N\) まで吹く．地点 \(N\) には JOI 君の家が建てられている．地点 \(0\) の標高は \(A_0 = 0\) であり，地点 \(i\) (\(1 \leqq i \leqq N\)) の標高は \(A_i\) である．

風は地表面に沿って吹き，高度の変化に応じて風の温度が変化する．海に接している地点 \(0\) での風の温度は \(0\) 度であり，すべての \(i\) (\(0 \leqq i \leqq N - 1\)) に対して，地点 \(i\) から地点 \(i + 1\) にかけての風の温度の変化はその時点における \(A_i\) と \(A_{i + 1}\) にのみ依存しており，以下のようになっている．

  • \(A_i < A_{i + 1}\) のとき，標高が \(1\) 上がるごとに風の温度は \(S\) 度下がる．
  • \(A_i \geqq A_{i + 1}\) のとき，標高が \(1\) 下がるごとに風の温度は \(T\) 度上がる．

IOI 国の領土では地殻変動が盛んである．あなたは，\(Q\) 日間の地殻変動のデータを入手した．\(j\) 日目 (\(1 \leqq j \leqq Q\)) には，\(L_j \leqq k \leqq R_j\) (\(1 \leqq L_j \leqq R_j \leqq N\)) を満たす地点の標高 \(A_k\) が \(X_j\) だけ変化する．\(X_j\) が非負のときは，標高が \(X_j\) だけ上がることを意味し，\(X_j\) が負のときは，標高が \(|X_j|\) だけ下がることを意味する．

あなたの仕事は，各地殻変動が起こった後の，JOI 君の家に吹く風の温度を求めることである．

課題

地殻変動が起きる前の標高と地殻変動の情報が与えられたとき，すべての整数 \(j\) (\(1 \leqq j \leqq Q\)) に対し，\(j\) 日目の地殻変動が起こった後の JOI 君の家に吹く風の温度を求めるプログラムを作成せよ．

Input

標準入力から以下の入力を読み込め．

  • \(1\) 行目には， \(4\) 個の整数 \(N, Q, S, T\) が空白を区切りとして書かれている．これらは，JOI 君の家が地点 \(N\) に建てられており，地殻変動の回数が \(Q\) であり，標高が \(1\) 上がるごとに風の温度が \(S\) 度下がり，\(1\) 下がるごとに \(T\) 度上がることを表す．
  • 続く \(N + 1\) 行のうちの \(i\) 行目 (\(1 \leqq i \leqq N + 1\)) には，地点 \(i - 1\) での地殻変動が起こる前の標高を表す整数 \(A_{i - 1}\) が書かれている．
  • 続く \(Q\) 行のうちの \(j\) 行目 (\(1 \leqq j \leqq Q\)) には，\(3\) 個の整数 \(L_j, R_j, X_j\) が空白を区切りとして書かれている．これらは，\(j\) 日目の地殻変動で地点 \(L_j\) から \(R_j\) までの標高が \(X_j\) だけ変化することを表す．

Output

出力は \(Q\) 行からなる．標準出力の \(j\) 行目 (\(1 \leqq j \leqq Q\)) には，\(j\) 日目の地殻変動が起こった後の JOI 君の家に吹く風の温度を出力せよ．

Constraints

すべての入力データは以下の条件を満たす．

  • \(1 \leqq N \leqq 200\,000\)．
  • \(1 \leqq Q \leqq 200\,000\)．
  • \(1 \leqq S \leqq 1\,000\,000\)．
  • \(1 \leqq T \leqq 1\,000\,000\)．
  • \(A_0 = 0\)．
  • \(-1\,000\,000 \leqq A_i \leqq 1\,000\,000\) (\(1 \leqq i \leqq N\))．
  • \(1 \leqq L_j \leqq R_j \leqq N\) (\(1 \leqq j \leqq Q\))．
  • \(-1\,000\,000 \leqq X_j \leqq 1\,000\,000\) (\(1 \leqq j \leqq Q\))．

Subtasks

小課題 1 [30 点]

以下の条件を満たす．

  • \(N \leqq 2\,000\)．
  • \(Q \leqq 2\,000\)．

小課題 2 [10 点]

  • \(S = T\) を満たす．

小課題 3 [60 点]

  • 追加の制限はない．

Examples

Sample input 1
3 5 1 2
0
4
1
8
1 2 2
1 1 -2
2 3 5
1 2 -1
1 3 5
Sample output 1
-5
-7
-13
-13
-18

最初，地点 \(0, 1, 2, 3\) の標高はそれぞれ \(0, 4, 1, 8\) である．\(1\) 日目の地殻変動の後，標高はそれぞれ \(0, 6, 3, 8\)となる．このとき，地点 \(0, 1, 2, 3\) での風の温度はそれぞれ \(0, -6, 0, -5\) となる．

Sample input 2
2 2 5 5
0
6
-1
1 1 4
1 2 8
Sample output 2
5
-35

この入力例は，小課題 \(2\) の条件を満たす．

Sample input 3
7 8 8 13
0
4
-9
4
-2
3
10
-9
1 4 8
3 5 -2
3 3 9
1 7 4
3 5 -1
5 6 3
4 4 9
6 7 -10
Sample output 3
277
277
322
290
290
290
290
370

Notes

JOI 2017 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source