An Animal Contest 6 P2 - G-Pop

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

Kyriakos Grizzly is organizing a G-Pop (Grizzly-Pop) concert for his Q friends! The concert consists of N shows where each show has a G-pop band performing in it. Note that a certain band may perform multiple times over the period of the N shows. Since Kyriakos' friends are very busy, the i^\text{th} of his friends can only attend the concerts from l_i to performance r_i (inclusive). Also, his friends will get bored if they listen to the same band more than once. Kyriakos wants to design a concert plan in which none of his friends gets bored. Also, since his friends are extremely impatient, Kyriakos wants to design a plan with the minimum number of band changes. A band change occurs when two different bands perform in consecutive concerts. In addition, he is trying to save money so this plan should minimize the number of distinct bands playing. Help Kyriakos determine a concert plan!


1 \le N \le 5 \times 10^5

0 \le Q \le \min(5 \times 10^5, \frac{N(N+1)}{2})

Input Specification

The first line of input will contain 2 spaced out integers N and Q. The next Q lines will each contain 2 integers with the i^\text{th} of these lines containing l_i and r_i.

Output Specification

The first line of output will contain a single integer K (1 \le K \le 10^9), the minimum number of different bands Kyriakos has to hire to be in his concert.

The final line of output will contain N spaced out integers each in the range [1, K], with the i^\text{th} integer denoting the id of the band performing at the i^\text{th} performance.

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


For each test case:

  • If you correctly determine the optimal K but you output an invalid plan, you will receive 20% of the available marks.
  • If you correctly determine the optimal K and you output a valid plan but you do not minimize the number of band changes you will receive another 30% of the marks.
  • If you correctly determine the optimal K and output a valid plan with the minimum number of band changes, you will receive the other 50% of the marks.
  • If your output is malformed in any way, you will automatically receive 0% of the available marks.

Your final score is the minimum score over all test cases.

Note: A valid plan is one that uses an optimal number of different bands, and makes sure that none of Kyriakos' friends get bored. A valid plan may not have the optimal number of band changes.

Sample Input

5 3
1 4
2 4
3 5

Sample Output

1 2 3 4 2


  • 9
    vsarca  commented on Aug. 5, 2023, 8:34 p.m.

    The bands may perform any number of times, I'm told...