레이스 기록 검증

NYPC 2022 · Round 1 연습문제

로그 파일이란 프로그램이 실행되면서 발생한 사건들을 기록한 파일을 의미한다. 카트라이더에서는 유저들이 레이스를 시작하고 종료하는 사건이 일어날 때마다, 어떤 시각에 어떤 유저가 레이스를 시작하거나 종료했는지에 대한 정보를 로그 파일에 기록한다. 이러한 로그 파일을 분석하면 게임 도중 발생한 에러나 부정 행위 등을 찾아낼 수 있다.

예를 들어, 어떤 유저가 시작한 레이스를 종료하기도 전에 새로운 레이스를 시작했다고 로그 파일에 기록되어 있다면, 게임 프로그램에 버그가 발생했다고 의심할 수 있다. 또한, 정상적인 레이스는 11분 이상이 걸리는데, 어떤 유저가 레이스를 시작한 지 3030초 만에 종료했다고 로그 파일에 기록되어 있다면, 그 유저가 정상적이지 않은 방법으로 게임을 플레이했다고 의심할 수 있다.

카트라이더에는 총 NN 명의 유저가 존재하며, 각각의 유저들은 11 번부터 NN 번까지의 번호를 가지고 있다. 프로그램은 시각 00초부터 로그 파일에 정보를 기록하기 시작한다. 만약 시각 tt초에 ii 번 유저가 레이스를 시작했다면, 로그 파일에는 t i 0이 기록된다. 만약 시각 tt초에 ii 번 유저가 레이스를 종료했다면, 로그 파일에는 t i 1이 기록된다. 로그 파일에는 이와 같은 정보가 총 MM 개 존재하며, 정보들은 사건이 발생한 시간 순서대로 기록되어 있다.

여러분은 카트라이더의 로그 파일을 입력으로 받아, 로그 파일의 기록이 올바른지 확인하는 프로그램을 작성해야 한다. 올바르지 않은 기록들은 다음과 같으며, 아래에 해당하지 않는 기록들은 모두 올바른 기록이다.

입력 형식

첫 줄에 유저의 수 NN과 로그 파일에 포함된 기록의 수 MM이 공백으로 구분되어 주어진다. (1N100;1 \le N \le 100; 1M2001 \le M \le 200)

둘째 줄부터 MM 개의 줄에 걸쳐 세 정수 tt, ii, ss가 공백으로 구분되어 주어진다.

tt는 유저가 레이스를 시작하거나 끝낸 시각을 의미한다. 시각은 초 단위이다. (0t<864000 \le t < 86\,400)

ii는 유저의 번호를 나타내는 11 이상 NN 이하의 정수이다. (1iN1 \le i \le N)

ii 번 유저가 시각 tt초에 레이스를 시작했을 경우, s=0s = 0이다. ii 번 유저가 시각 tt초에 레이스를 종료했을 경우, s=1s = 1이다.

기록은 시각(tt)이 감소하지 않는 순서대로 주어진다. 또한, 같은 시각에 한 유저와 관련된 사건이 두 번 이상 일어나지 않는다. 즉, 한 유저가 레이스를 종료하는 것과 동시에 새로운 레이스를 시작하는 등의 사건은 일어나지 않는다. 단, 서로 다른 유저와 관련된 사건은 같은 시각에 일어날 수도 있다. 즉, 11 번 유저가 레이스를 종료하는 것과 동시에 22 번 유저가 레이스를 시작할 수 있다.

NN 명의 유저 중에서 로그 파일에 한 번도 등장하지 않는 유저가 있을 수 있다.

출력 형식

입력으로 주어진 로그 파일의 기록이 올바르다면 YES, 올바르지 않다면 NO를 출력한다. 출력은 대소문자를 구별하지 않는다. 즉, 만약 정답이 YES인 경우, yesyES를 출력해도 정답으로 인정한다.

예제 1

입력

3 6 100 1 0 200 3 0 300 2 0 400 1 1 500 2 1 600 3 1

출력

YES

예제 2

입력

1 3 1023 1 0 1102 1 0 1296 1 1

출력

NO

예제 3

입력

1 3 7624 1 0 7700 1 1 7791 1 1

출력

NO

예제 4

입력

1 2 10 1 0 47 1 1

출력

NO

예제 5

입력

1 1 37 1 0

출력

NO

예제 설명

예제 1에서, 11 번 유저는 시각 100100초에 시작한 레이스를 시각 400400초에 종료했다. 22 번 유저는 시각 300300초에 시작한 레이스를 시각 500500초에 종료했고, 33 번 유저는 시각 200200초에 시작한 레이스를 시각 600600초에 종료했다. 모든 유저가 레이스를 시작하고 나서 6060초보다 같거나 긴 시간이 지난 이후에 종료했다. 따라서 주어진 로그 파일의 기록은 올바르다.

예제 2에서, 11 번 유저는 시각 10231\,023초에 레이스를 시작한 뒤, 그 레이스를 종료하기도 전에 시각 11021\,102초에 새로운 레이스를 시작했다. 따라서 로그 파일의 기록은 올바르지 않다.

예제 3에서, 11 번 유저는 시각 76247\,624초에 시작한 레이스를 시각 77007\,700초에 종료한 뒤, 새로운 레이스를 시작하기도 전에 시각 77917\,791초에 다시 레이스를 종료했다. 따라서 로그 파일의 기록은 올바르지 않다.

예제 4에서, 11 번 유저는 시각 1010초에 레이스를 시작한 뒤, 3737초 후인 시각 4747초에 종료했다. 레이스를 5959초 이내에 종료했으므로, 로그 파일의 기록은 올바르지 않다.

예제 5에서, 11 번 유저는 시각 3737초에 레이스를 시작한 뒤 종료하지 않았다. 따라서 로그 파일의 기록은 올바르지 않다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 17

N=1;N = 1; M2M \le 2

종류 2: 29

N=1N = 1

종류 3: 19

모든 유저는 로그 파일에 두 번 이하로 등장한다.

종류 4: 35

추가적인 제한 조건이 없음.

해설