루미 알고리즘

#1560플래티넘Waterfall

PO 2023 결선코딩출제 Ivar Källström, Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Alexander likes water. Therefore, it's no surprise that he is fond of rushing water. This might explain why he wants to create his own waterfall. Just imagine, water cascading endlessly!

He has found a cliff face that he believes will make the perfect waterfall after he adds some water. The cliff face can be modeled as an R × C grid, where N cells have an outcropping cliff. The rows are numbered from 0 to R-1 from bottom to top, and the columns are numbered from 0 to C-1 from left to right. At columns -1 and C there is a wall that water cannot pass through. Alexander plans to pour water from above so that it flows down in K columns.

The water spreads in the grid according to the following rules: if the cell below the water is empty, it spreads there. If there is a cliff in the way, it instead spreads to the right and left. If there is a cliff in the way to the right or left, it does not spread in that direction. This also applies to the water being poured from above, i.e., if water is poured into column i and the top row has a cliff in column i, it is as if water is also being poured from above in columns i - 1 and i + 1, provided those columns are within the grid.

However, Alexander does not want to cause a flood because then all the water will stand still in the end. Water that stands still is, of course, less exciting than rushing water. Therefore, he wants your help to write a program that calculates how many columns have water in them in the bottom row of the grid.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: An illustration of the flow in samples 1 and 2. The red frame marks the end of the cliff face.

Input

The first line contains two integers R, C (2 ≤ R ≤ 10^9, 1 ≤ C ≤ 10^9), the number of rows and columns that make up the mountain.

The second line contains two integers K, N (1 ≤ K, N ≤ 10^5), the number of columns with water and the number of cliffs protruding from the mountain.

Following this are K lines, where the ith line contains the integer V_i (0 ≤ V_i ≤ C-1), indicating that water flows down along column V_i from above the grid. It is guaranteed that all V_i are unique.

Afterward, there are N lines where each line i contains two integers A_i (1 ≤ A_i ≤ R-1) and B_i (0 ≤ B_i ≤ C-1), representing the row and column where the ith cliff is located. These positions are also unique.

Output

Print an integer: the number of columns that contain water in the bottom row of the grid.

Scoring

Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.

GroupPointsConstraints
120R · C ≤ 1000
230Cliffs can't touch each other diagonally, horizontally or vertically.
320Cliffs can't touch each other diagonally.
430No additional constraints.

예제

예제 1

입력
8 6
3 4
1
4
5
1 3
2 2
5 1
5 5
출력
3

예제 2

입력
8 6
1 8
3
2 1
1 2
2 3
5 2
5 3
5 4
5 5
6 5
출력
1

예제 3

입력
5 4
1 3
3
1 1
2 2
3 3
출력
1

출처 표기

출처: Programmeringsolympiaden 2023년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.