루미 알고리즘

#1419플래티넘Snömurskontrollant

PO 2017 결선코딩출제 Johan Sannemo스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

PO-juryn kan inte programmera. Efter fiaskot i onlinekvalet, där den trasiga domaren för problemet Snömur (https://pokval16.kattis.com/problems/pokval16.snomur) råkade ge Island vinsten med 211.58 av 100 poäng på problemet har juryn bestämt sig för att outsource:a sina domare till folk som faktiskt kan koda – PO-finalister.

Problemet var som följer:

Sverige ska bygga en snömur, av en viss bredd W. Som byggmaterial finns det ett antal snöblock som alla har höjden 1, men kan ha olika bredder. När muren konstrueras måste varje block uppfylla följande regel: på raden under blocket, på de två positioner blocket har sina ändpunkter, måste det ligga ett block precis till höger och vänster om punkten, undantaget början och slutet på en rad, där det istället måste finnas en ändpunkt på varje rad (se den vänstra, näst översta muren i Figur 1 där detta saknas på översta raden).

Det får dessutom inte finnas hålrum på samma position på två direkt efterföljande rader i muren (den tomma raden precis ovanför muren räknas inte).

Följande bild illustrerar några otillåtna (vänster) och tillåtna (höger) murar:

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

Figur 1: Ett antal otillåtna (vänster) och tillåtna (höger) murar.

Givet ett förslag på hur muren ska se ut, avgör om muren är en tillåten mur.

Indata

Den första raden innehåller två heltal W och H - bredden och höjden på muren.

De följande H raderna beskriver raderna i muren. Varje rad börjar med ett heltal B ≥ 1, antalet block på raden. Detta följs av B par av heltal P_j, L_j, den (noll-indexerade) positionen och längden för det j:te blocket på raden. Dessa kommer ges i stigande P_j-ordning, d.v.s från vänster till höger. Inga block kommer överlappa eller ligga utanför muren.

Raderna är givna underifrån - dvs den första raden i indata är den understa raden i muren.

Låt summan av antalet block över alla rader vara N. Detta tal har gränser i poängsättningstabellen.

Utdata

Du ska skriva ut YES om muren är tillåten, och NO om den inte är det.

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Övrigt
1311 ≤ N, W, H ≤ 100000Inga hål förekommer direkt över ett annat hål
2341 ≤ N, W, H ≤ 1000
3351 ≤ N, W, H ≤ 100000

Förklaring av exempel

De fyra första exemplen motsvarar de fyra otillåtna murarna till vänster i bilden. De sista fyra exemplen motsvarar de fyra tillåtna murarna till höger i bilden.

예제

예제 1

입력
10 3
1 0 10
2 0 4 6 4
2 0 3 7 3
출력
NO

예제 2

입력
10 3
1 0 10
2 0 4 6 4
1 0 9
출력
NO

예제 3

입력
10 3
1 0 10
2 0 4 6 4
2 0 5 5 5
출력
NO

예제 4

입력
10 3
1 0 10
2 0 4 6 4
2 0 4 4 6
출력
NO

예제 5

입력
10 3
1 0 10
2 0 4 6 4
1 0 10
출력
YES

예제 6

입력
10 3
1 0 10
2 0 4 6 4
2 0 7 8 2
출력
YES

예제 7

입력
10 3
2 0 2 3 7
2 0 4 6 4
1 0 10
출력
YES

예제 8

입력
10 3
1 0 10
3 0 4 4 2 9 1
2 0 4 4 6
출력
YES

출처 표기

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