시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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

출처