눈벽 검사기

면접 대비

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

요약

아래에서 위로 적힌 행들을 입력받아, 각 블록의 양 끝이 아래 행에서 받쳐지는지와 연속한 두 행에 같은 위치의 빈칸이 없는지 판별합니다.

난이도: 쉬움10점 중 3점
유형: 배열, 구현
정답자: 아직 제출이 없습니다

문제

스웨덴은 폭이 $W$ 인 눈벽을 쌓으려 한다. 재료는 높이가 1이고 폭은 블록마다 다를 수 있는 눈블록이다. 벽을 쌓을 때 모든 블록은 다음 규칙을 만족해야 한다. 블록 바로 아래 줄에서, 블록의 두 끝점이 놓인 위치마다 그 점의 바로 오른쪽과 왼쪽에 블록이 있어야 한다. 다만 줄의 시작과 끝은 예외이며, 이 자리에는 대신 모든 줄에 끝점이 있어야 한다. 그림 1의 왼쪽, 위에서 두 번째 벽을 보라. 맨 윗줄에는 이 조건이 빠져 있다.

또한 벽에서 바로 이웃한 두 줄이 같은 위치에 빈 칸을 가지면 안 된다. 벽 바로 위의 빈 줄은 계산하지 않는다.

아래 그림은 허용되지 않는 벽(왼쪽)과 허용되는 벽(오른쪽)의 예이다.

그림 1: 허용되지 않는 벽(왼쪽)과 허용되는 벽(오른쪽)의 예.

주어진 벽 설계가 허용되는 벽인지 판정하라.

입력

첫 줄에 벽의 폭 $W$ 와 높이 $H$ 가 두 정수로 주어진다.

이어지는 $H$ 개의 줄은 벽의 각 줄을 나타낸다. 각 줄은 그 줄에 있는 블록 수 $B \ge 1$ 로 시작한다. 그 뒤에 $B$ 쌍의 정수 $P_j, L_j$ 가 이어진다. 이는 그 줄의 $j$ 번째 블록의 (0부터 세는) 위치와 길이이다. 쌍은 $P_j$ 의 오름차순, 즉 왼쪽에서 오른쪽 순서로 주어진다. 블록끼리 겹치거나 벽 밖으로 나가는 경우는 없다.

줄은 아래에서 위 순서로 주어진다. 입력의 첫 줄이 벽의 가장 아래 줄이다.

모든 줄의 블록 수 합을 $N$ 이라 한다.

출력

벽이 허용되는 벽이면 YES, 아니면 NO를 출력하라.

제한

$1 \le N, W, H \le 100\,000$

힌트

처음 네 예제는 그림 왼쪽의 허용되지 않는 네 벽에 해당한다. 마지막 네 예제는 그림 오른쪽의 허용되는 네 벽에 해당한다.

예제5

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