페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6125

쓰나미 5s 1024MB

문제

지구 온난화와 환경 위기로 인해 자연 재해에 대비해 생존 계획을 세워야 한다. 이번에는 쓰나미에 대한 대피 매뉴얼을 만들어 보자.

바다선은 x축과 평행한 직선 y=k로 나타낼 수 있다. 보통 k는 0이지만, 쓰나미가 발생하면 양의 실수가 된다.

도시에는 점 (p_i,q_i)로 표시된 N개의 대피 장소가 있다. 이 장소들에서는 동시에 모이고 움직인다. 또한 각 장소에는 r_i가 주어지는데, 이는 그 장소로 가는데 걸리는 시간(분 단위)을 의미한다.

대피에 방해가 되는 장애물이 있다. 단순화를 위해 장애물은 x축과 평행한 직선이라고 가정한다.

총 M개의 장애물이 (s_i,e_i,y_i,t_i)로 주어지는데, 이는 점 (s_i,y_i)와 (e_i,y_i)를 잇는 선분으로, 이를 횡단하는데 t_i​분이 걸린다는 것을 의미한다. 끝점에서도 t_i분이 걸린다는 것에 주의하라. 장애물과 대피 장소는 겹치지 않는다.

하지만 장애물끼리는 겹칠 수 있다. 이 경우, 겹친 장애물을 횡단하는 시간은 겹친 t_i​들의 합이 된다. 예를 들어, 장애물이 (1,4,2,5)와 (3,5,2,7)이라면, x=1에서 횡단하는데 5분, x=3에서 횡단하는데 5+7=12분, x=5에서 횡단하는데 7분이 걸린다.

우리는 y=Y에 도달할 때까지 위쪽(즉, +y 방향)으로만 움직인다. 위쪽으로 움직이면서 x좌표도 바꿀 수 있다. 현재 y좌표가 i와 i+1 사이일 때 x축을 따라 한 좌표 이동하는데 c_i분이 걸린다. 예를 들어 c_3=5이고 y=3.5일 때 x좌표를 10에서 6으로 바꾸면 5×∣10−6∣=20분이 걸린다.

우리는 정수 x좌표로만 움직일 수 있으며, 정수 y좌표에서는 x좌표를 바꾸지 않는다. 이것이 유일한 제약사항이다. 원한다면 x=−100이나 x=10^{100}으로도 움직일 수 있다.

또한 c_1,...,c_{Y−1}은 증가하는 수열이라는 것에 주의하라. y가 증가함에 따라 사람 수도 증가하기 때문에, 사이를 움직이기가 어려워지기 때문이다.

대피 매뉴얼은 다음과 같다:

  • 1. 적절한 대피 장소로 이동한다.

  • 2. 그 장소에서 시작하여 주어진 제약 조건 하에 y=Y로 이동한다. 우리는 단순히 위쪽으로 움직이는 시간은 고려하지 않는다. 왜냐하면 우리가 시작하는 대피 장소에 관계없이 거의 일정하기 때문이다. 우리는 대피 장소로 이동하는 시간, 수평으로 움직이는 시간, 장애물을 횡단하는 시간만 고려한다.

(1,Y), (2,Y), …, (X,Y)로 대피하는데 걸리는 최소 시간(분 단위)을 각각 계산해 보자.


입력

첫 줄에는 두 개의 공백으로 구분된 정수 X와 Y가 주어진다.

두 번째 줄에는 두 개의 공백으로 구분된 정수 N과 M이 주어진다.

다음 N개의 줄에는 각각 세 개의 공백으로 구분된 정수 p_i, q_i​, r_i​가 주어지는데, 이는 i번째 대피 장소를 의미한다.

다음 M개의 줄에는 각각 네 개의 공백으로 구분된 정수 s_i, e_i​, y_i​, t_i​가 주어지는데, 이는 i번째 장애물을 의미한다.

마지막 줄에는 Y−1개의 공백으로 구분된 정수 c_1, c_2​, …, c_{Y−1}​이 주어진다. c_i는 y좌표가 (i,i+1) 사이일 때 x좌표를 바꾸는 시간을 의미한다.

제한

  •  3\leq X, Y\leq 2\times 10^5

  •  1\leq N\leq 2\times 10^5

  •  0\leq M\leq 2\times 10^5

  •  1\leq p_i\leq X, 1\leq q_i<Y, 0\leq r_i\leq 10^{15}

  •  1\leq s_i\leq e_i\leq X, 2\leq y_i<Y, 0\leq t_i\leq 10^9

  •  0\leq c_1\leq c_2\leq ...\leq c_{Y-1}\leq 10^6


출력

X개의 줄을 출력한다. i번째 줄에는 점 (i,Y)로 대피하는데 걸리는 최소 시간(분 단위)을 하나의 정수로 출력한다.


부분문제

번호 점수 조건
#111점

  • X≤2000

  • Y≤2000

#27점

  • X≤400

  • N≤50\ 000

  • M\leq 400

#310점

  • X≤400

  • N≤50\ 000

  • M\leq 50\ 000

#423점

  • M=0

#525점

  • c_1 = c_2 = ...= c_{Y-1}

#624점

  • 추가 제한 조건이 없다.


예제 #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

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

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

출처

2023 KAIST RUN Spring Contest
로그인해야 코드를 작성할 수 있어요.