13389번 - RMQ

구간의 최댓값(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이 주어진다. 그 다음, 각각의 쿼리 (L_i, R_i)와 해당하는 쿼리의 정답 A_i가 주어진다. 이때, 입력으로 주어진 쿼리를 모두 만족시키는 수열 P가 존재하는지 아닌지 구하는 프로그램을 작성하시오.

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

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

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