만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

쓰나미

시간 제한4초메모리 제한1024 MB

요약
장애물 구간의 횡단 비용과 높이별 횡이동 비용이 주어질 때, x 좌표 1부터 X까지 각각에서 y=Y에 도달하는 최소 시간을 구합니다.
난이도

어려움10점 중 8점

유형
동적 계획법, 세그먼트 트리, 정렬
정답자
아직 제출이 없습니다

문제

지구 온난화와 환경 위기 때문에 가능한 자연재해에 대비한 계획을 세워야 합니다. 이번에는 쓰나미 대피 매뉴얼을 만듭니다.

해안선은 x축에 평행한 직선 y=ky=k입니다. 평소에는 kk가 00이지만, 쓰나미가 발생하면 kk는 양의 실수가 됩니다.

우리 도시에는 NN개의 대피 장소가 있으며, 각 장소는 점 (pi,qi)(p_i, q_i)로 나타냅니다. 사람들은 이 장소들에 모였다가 동시에 이동합니다. 각 장소에는 도달하는 데 걸리는 시간 rir_i(분)가 주어집니다.

대피를 방해하는 장애물이 있습니다. 단순하게 하기 위해 장애물은 모두 x축에 평행한 선분이라고 가정합니다. MM개의 장애물은 (si,ei,yi,ti)(s_i, e_i, y_i, t_i)로 주어지며, ii번째 장애물은 (si,yi)(s_i, y_i)와 (ei,yi)(e_i, y_i)를 잇는 선분입니다. 이 선분을 건너는 데 tit_i분이 걸리며, 끝점에서도 건너는 데 tit_i분이 걸립니다. 장애물과 대피 장소가 겹치는 경우는 없습니다.

장애물끼리는 겹칠 수 있습니다. 겹친 부분을 건너는 시간은 겹친 장애물들의 tit_i를 더한 값입니다. 예를 들어 장애물 (1,4,2,5)(1, 4, 2, 5)와 (3,5,2,7)(3, 5, 2, 7)이 있으면, x=1x=1에서는 5분, x=3x=3에서는 5+7=125+7=12분, x=5x=5에서는 7분이 걸립니다.

안전 지대인 y=Yy=Y에 도달할 때까지 위쪽(+y 방향)으로만 이동합니다. 위로 올라가는 동안 x좌표도 바꿀 수 있습니다. 현재 y좌표가 ii와 i+1i+1 사이에 있을 때 x좌표를 1만큼 바꾸는 데 cic_i분이 걸립니다. 예를 들어 c3=5c_3=5일 때 y=3.5y=3.5에서 x좌표를 1010에서 66으로 옮기면 5×∣10−6∣=205 \times |10-6| = 20분이 걸립니다.

x좌표는 정수로만 옮길 수 있습니다. 정수 y좌표에서는 x좌표를 바꾸지 않는다고 가정해도 됩니다. 이 조건이 이동에 대한 유일한 제약입니다. 원한다면 x=−100x=-100이나 x=10100x=10^{100}으로 이동해도 됩니다.

수열 c1,…,cY−1c_1, \ldots, c_{Y-1}은 비감소 수열입니다. y가 커질수록 사람이 많아져서 옆으로 이동하기가 더 어려워집니다.

대피 매뉴얼은 다음과 같습니다.

  1. 적절한 대피 장소로 이동합니다.
  2. 그 장소에서 위의 제약 아래 y=Yy=Y까지 이동합니다.

위로 곧장 올라가는 시간은 시작 장소와 관계없이 거의 일정하므로 계산에 넣지 않습니다. 대피 장소까지 이동하는 시간, 수평 이동 시간, 장애물을 건너는 시간만 고려합니다.

(1,Y)(1, Y), (2,Y)(2, Y), ..., (X,Y)(X, Y)에 각각 도달하는 최소 시간(분)을 구하세요.

입력

첫 번째 줄에는 공백으로 구분된 두 정수 XX와 YY가 주어집니다.

두 번째 줄에는 공백으로 구분된 두 정수 NN과 MM이 주어집니다.

이어지는 NN개의 줄에는 ii번째 대피 장소를 나타내는 공백으로 구분된 세 정수 pip_i, qiq_i, rir_i가 한 줄에 하나씩 주어집니다.

이어지는 MM개의 줄에는 ii번째 장애물을 나타내는 공백으로 구분된 네 정수 sis_i, eie_i, yiy_i, tit_i가 한 줄에 하나씩 주어집니다.

마지막 줄에는 공백으로 구분된 Y−1Y-1개의 정수 c1,c2,…,cY−1c_1, c_2, \ldots, c_{Y-1}이 주어집니다. cic_i는 y좌표가 ii와 i+1i+1 사이에 있을 때 x좌표를 바꾸는 속도입니다.

출력

XX개의 줄을 출력합니다. ii번째 줄에는 (i,Y)(i, Y)에 도달하는 최소 시간(분)을 정수 하나로 출력합니다.

제한

  • 3≤X,Y≤2×1053 \leq X, Y \leq 2 \times 10^5
  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 0≤M≤2×1050 \leq M \leq 2 \times 10^5
  • 1≤pi≤X1 \leq p_i \leq X, 1≤qi<Y1 \leq q_i < Y, 0≤ri≤10150 \leq r_i \leq 10^{15}
  • 1≤si≤ei≤X1 \leq s_i \leq e_i \leq X, 2≤yi<Y2 \leq y_i < Y, 0≤ti≤1090 \leq t_i \leq 10^9
  • 0≤c1≤c2≤⋯≤cY−1≤1060 \leq c_1 \leq c_2 \leq \cdots \leq c_{Y-1} \leq 10^6

예제3

  1. 예제 1

    입력
    6 10
4 2
3 1 9
6 1 2
1 1 5
4 3 4
1 4 8 2
1 2 8 5
3 4 6 6 6 6 7 10 10
    예상 출력
    12
15
11
6
5
2

  2. 예제 2

    입력
    10 10
5 6
6 1 3
2 2 5
10 2 5
2 1 7
9 1 8
5 8 3 5
2 4 9 2
2 7 4 20
6 9 6 6
8 9 4 19
3 10 7 5
0 3 3 4 6 8 9 9 10
    예상 출력
    3
9
18
22
24
30
26
22
16
8

  3. 예제 3

    입력
    10 12
3 7
3 1 8
7 2 4
1 1 7
1 2 6 14
5 10 6 1
1 10 6 5
2 10 9 3
2 7 5 16
8 10 7 10
3 7 9 10
0 1 1 1 3 4 6 8 9 9 9
    예상 출력
    11
18
27
34
33
30
27
23
22
16