Yet Another Contest 3 P3 - Topology

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 1.0s
Java 2.0s
Python 4.0s
Memory limit: 512M

Authors:
Problem types

After getting bored of playing video games, Mike decided to go hiking. Like any good hiker, he brought a map along with him. However, shortly after setting out for the hike, Mike was caught in a rainstorm. Once he found shelter under a nearby tree, Mike realized his map had gotten drenched as well!

Determined to finish his hike, Mike wants you to reconstruct the map. The map is represented as an array of integers, each indicating the elevation at a particular point. Remembering that certain sections of the map were uphill or downhill, Mike will give you M requirements, each in the form t_i l_i r_i:

  • If t_i = 1, the subarray from index l_i to index r_i is strictly increasing.
  • If t_i = 2, the subarray from index l_i to index r_i is strictly decreasing.

Mike also has some additional requirements for the map: First of all, he tells you that the trail is never flat, so no two adjacent elements can be equal. Second of all, each element must be a positive integer not exceeding 10^9. Third of all, the maximum element of the array should be as small as possible.

Help Mike reconstruct his map, or tell him that it is impossible to do so.

Constraints

2 \le N \le 10^6

1 \le M \le 10^6

t_i \in \{1, 2\}

1 \le l_i < r_i \le N

Subtask 1 [50%]

2 \le N \le 5000

1 \le M \le 5000

If your submission outputs a valid map but does not minimize the maximum element, you will receive 25\% out of the 50\% of points available for this subtask.

Subtask 2 [50%]

No additional constraints.

If your submission outputs a valid map but does not minimize the maximum element, you will receive 25\% out of the 50\% of points available for this subtask.

Input Specification

The first line contains 2 integers N and M.

The i-th of the following M lines each contain 3 integers t_i, l_i, r_i, describing a requirement as specified in the statement.

Output Specification

If no valid output exists, output -1.

Otherwise, output one line containing N positive integers that satisfy all requirements. Each element must be within the range [1, 10^9], and no two adjacent elements can be equal.

If there are multiple valid answers, you may output any of them.

Sample Input 1

5 2
1 1 3
2 3 5

Sample Output 1

1 2 3 2 1

Sample Input 2

3 3
1 1 2
1 2 3
2 1 3

Sample Output 2

-1

Comments

There are no comments at the moment.