시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 26 6 6 26.087%

문제

구간의 최대값(RMQ) 문제는 다음과 같다.

1부터 N까지 정수로 이루어진 순열 P가 주어진다. 이 때, 각각의 쿼리는 1 ≤ L ≤ R ≤ N을 만족하는 (L, R) 형식이며, P의 L번째 수부터 R번째 수까지 중에서 최대값을 찾아 출력하라는 의미이다.

예를 들어, P = (3, 1, 4, 2, 5)인 경우에

  • 쿼리 (1, 2)의 답은 max(3, 1) = 3 이다.
  • 쿼리 (2, 4)의 답은 max(1, 4, 2) = 4 이다.
  • 쿼리 (4, 5)의 답은 max(2, 5) = 5 이다.

우리는 RMQ 문제를 역으로 풀어보려고 한다.

정수 N과 쿼리의 개수 M이 주어진다. 그 다음, 각각의 쿼리 (Li, Ri)와 해당하는 쿼리의 정답 Ai가 주어진다. 이 때, 입력으로 주어진 쿼리를 모두 만족시키는 수열 P가 존재하는지 아닌지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 쿼리의 개수 M이 주어진다. (1 ≤ N ≤ 1,000,000,000, 1 ≤ M ≤ 50)

둘째 줄부터 M개의 줄에 쿼리의 정보 Li, Ri와 정답 Ai가 주어진다. (1 ≤ Li ≤ Ri ≤ N, 1 ≤ Ai ≤ N)

출력

입력으로 주어진 쿼리를 만족시키는 순열이 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1

5 3
1 2 3
2 4 4
4 5 5

예제 출력 1

1

예제 입력 2

5 3
1 1 3
2 2 3
3 3 3

예제 출력 2

0

예제 입력 3

600 6
1 100 100
101 200 200
201 300 300
301 400 400
401 500 500
501 600 600

예제 출력 3

1

예제 입력 4

1000000000 2
1234 5678 10000
1234 5678 20000

예제 출력 4

0

예제 입력 5

8 8
1 1 4
2 2 8
3 3 2
4 4 5
5 5 6
6 6 3
7 7 7
8 8 1

예제 출력 5

1

예제 입력 6

1000000000 1
1 1000000000 19911120

예제 출력 6

0

출처