아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Restore Array

시간 제한0.6초메모리 제한1024 MB

요약
이진 배열의 각 부분 배열에서 k번째로 작은 값에 대한 제약이 주어질 때, 모든 제약을 만족하는 배열을 하나 구하거나 불가능함을 판정한다.
난이도

보통10점 중 7점

유형
그리디, 정렬, 누적 합, 구현
정답자
아직 제출이 없습니다

문제

Your task is to determine one possible binary array A of length N that abides by M given constraints of the form:

  • (l, r, k, value) - the k-th smallest element in subarray A[l..r] is value (0 ≤ l ≤ r < N, 1 ≤ k ≤ r - l + 1, 0 ≤ value ≤ 1). Please note that array A is 0-indexed.

입력

The first line of input contains two integers N and M (1 ≤ N ≤ 5 000, 1 ≤ M ≤ 10 000) - the length of array A and the number of constraints.

The next M lines describe the constraints. Each line contains four integers li, ri, ki, valuei, describing the i-th constraint.

출력

The first line of the output contains N integers - one possible binary array A. If there are several that abide by all M constraints you may output any of them. If there is no such array you must instead output the single integer -1.

힌트

There are several binary arrays that abide by all the constraints. One of them is 0 1 0 0 because:

  1. The 2-nd smallest element among 0 1 0 0 is 1.
  2. The 2-nd smallest element among 0 1 0 0 is 0.
  3. The 1-st smallest element among 0 1 0 0 is 0.
  4. The 1-st smallest element among 0 1 0 0 is 0.
  5. The 1-st smallest element among 0 1 0 0 is 0.

예제1

  1. 예제 1

    입력
    4 5
0 1 2 1
0 2 2 0
2 2 1 0
0 1 1 0
1 2 1 0
    예상 출력
    0 1 0 0