시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 41 | 9 | 9 | 25.714% |
구간의 최댓값(RMQ) 문제는 다음과 같다.
1부터 N까지 정수로 이루어진 순열 P가 주어진다. 이때, 각각의 쿼리는 1 ≤ L ≤ R ≤ N을 만족하는 (L, R) 형식이며, P의 L번째 수부터 R번째 수까지 중에서 최댓값을 찾아 출력하라는 의미이다.
예를 들어, P = (3, 1, 4, 2, 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을 출력한다.
5 3 1 2 3 2 4 4 4 5 5
1
5 3 1 1 3 2 2 3 3 3 3
0
600 6 1 100 100 101 200 200 201 300 300 301 400 400 401 500 500 501 600 600
1
1000000000 2 1234 5678 10000 1234 5678 20000
0
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
1
1000000000 1 1 1000000000 19911120
0