루미 알고리즘

#1491다이아Fladdermusen

PO 2020 훈련 캠프코딩출제 Nils Gustafsson, David Wärn스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Fladdermusen Båtman bor i en stor grotta med många andra fladdermöss. Båtman har precis fått ett nytt jobb som den officiella fladdermus-brevbäraren. Detta betyder att Båtman måste leverera brev mellan vissa punkter i grottan.

Grottan är två-dimensionell och rektangulärformad med höjd H och bredd W cm. Den är också fylld med totalt N stycken stalagmiter och stalaktiter. En stalagmit är en vertikal droppstenformation som växer upp från grottans golv, och en stalaktit är en vertikal droppstenformation som växer ner från grottans tak. Både stalagmiterna och stalaktiterna i grottan är oändligt tunna, men går inte att flyga igenom.

Båtman har fått en lista på Q stycken brev som måste levereras. Varje brev måste hämtas upp från en punkt i grottan och levereras till en annan punkt. Båtman undrar nu, för varje brev, hur långt hen måste flyga för att leverera det från startpunkten till ändpunkten, och ber dig om hjälp för att räkna ut detta.

Fladdermöss (inkluderat Båtman) kan endast flyga rakt upp, rakt ner, rakt vänster och rakt höger, men kan byta mellan dessa fyra rikntningar när som helst. (Läsaren kanske känner igen att vi är intresserade av Manhattan-avstånd i det här problemet.) Båtman kan alltså exempelvis flyga 0.4 cm till höger, och sen byta till att flyga 4.3 cm uppåt.

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

Figur 1: Illustration av första exempelfallet. Den prickade linjen visar en möjlig kortaste flygväg av längd 12 för att leverera det första brevet.

Indata

Den första raden innehåller de fyra heltalenn N,Q,H,W (1 ≤ N, Q ≤ 2 · 10^5, 1 ≤ H,W ≤ 10^9). Därefter följer N rader som är på någon av följande former:

  • 1 x y, vilket betyder att det finns en stalagmit som växer upp från punkten (x,0) till punkten (x,y).
  • 2 x y, vilket betyder att det finns en stalaktit som växer ner från punkten (x,H) till punkten (x,y).

Ingen stalagmit/stalaktit når hela vägen från taket till botten, och stalagmiterna/stalaktiterna är alla helt inuti grottan, d.v.s. 1 ≤ x_i < W och 1 ≤ y_i < H.

Därefter följer Q rader med fyra heltal x_1,y_1,x_2,y_2 (1 ≤ x_1,x_2 < W, 1 ≤ y_1,y_2< H) vilket representerar att ett brev ska levereras från punkten (x_1,y_1) till punkten (x_2,y_2).

Det är garanterat att alla x-koordinater i indatan är unika.

Utdata

Ditt program ska skriva ut Q rader, ett för varje brev. Den i:e raden ska innehålla ett heltal som är den minsta sträckan Båtman måste flyga för att leverera det i:e brevet.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

GruppPoängvärdeGränser
115N,Q ≤ 100 och H,W ≤ 500
220N,Q ≤ 2000 och H,W ≤ 2 · 10^6
325Det finns max 15 stalaktiter
440Inga ytterligare begränsningar

예제

예제 1

입력
3 1 5 7
1 2 4
2 3 2
1 5 3
1 2 6 1
출력
12

예제 2

입력
3 3 30 30
1 10 10
1 15 5
2 20 20
5 15 25 15
6 6 4 4
16 1 14 1
출력
20
4
10

출처 표기

출처: Programmeringsolympiaden 2020년 훈련 캠프 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.