Help with a problem

Revision en1, by RedSnowstorm, 2018-11-20 13:11:13

So sorry if I'm not using this feature properly, I was struggling with a problem and thought this would be a good place to ask for help. So here's the problem:

There are N light bulbs. Initially, all of them are turned off. You are given M switches with which you can switch the light bulbs on and off. The i-th switch will switch all the light bulbs in the subsequence starting at A[i] and ending at B[i] (All the turned off light bulbs are switched on and all the switched on ones are turned off).

You are also given a number X. Your job is to end with the light bulbs from 1 to X on, and all the ones from X+1 to N off, using the minimum number of switches possible.

Output the minimum number of switches to achieve the goal. If it is not possible to achieve the goal, output -1.

The input file are the numbers N M X followed by M (the number of switches) lines in which the i th line is A[i] and B[i] (the parameters for the switches)

N<=100 000 M<=200 000 example: IN OUT 5 3 4 3 1 3 3 4 3 3

History

Revisions

Rev. Lang. By When Δ Comment
en1 RedSnowstorm 2018-11-20 13:11:13 1144 Initial revision (published)