Woburn Challenge 2018-19 Round 4 - Senior Division
Billy has been having a great time playing a demo of Nintendo's next highly-anticipated 3D platforming game, Super Luigi Odyssey.
One challenge in the game sees Luigi trapped in a long hallway, which can be represented as a number line with positions increasing towards the rightwards direction. There are ~N~ ~(1 \le N \le 250\,000)~ platforms in it, with the ~i~-th one at position ~P_i~ ~(0 \le P_i \le 10^9)~ and at a height of ~H_i~ ~(1 \le H_i \le 10^9)~ metres. No two platforms are at the same position. Luigi begins on platform ~1~ (note that this is not necessarily the leftmost platform).
Much to Luigi's concern, the hallway is filled with some deadly lava. Initially, the lava reaches up to a height of ~0.5~ metres. At any point, a platform is considered to be submerged in lava if the lava's height exceeds the platform's height.
A sequence of ~M~ ~(1 \le M \le 250\,000)~ events will then occur, each having one of three possible types. The type of the ~i~-th event is described by the integer ~E_i~ ~(1 \le E_i \le 3)~.
- If ~E_i = 1~, then the lava's height will increase by ~X_i~ ~(-10^9 \le X_i \le 10^9)~ metres. It's guaranteed that this will not cause the lava's height to become negative. If this causes Luigi's current platform to become submerged, then he will immediately perish.
- If ~E_i = 2~, then ~X_i~ ~(1 \le X_i \le N)~ lasers in a row will be fired at Luigi. Each laser will force him to jump to the next non-submerged platform to the left of his current one. If there's no such platform, then he'll instead be forced to jump into the lava and perish.
- If ~E_i = 3~, then similarly ~X_i~ ~(1 \le X_i \le N)~ lasers in a row will be fired at Luigi, with each one forcing him to jump to the next non-submerged platform (if any) to the right rather than the left.
Luigi is not allowed to move between platforms aside from being forced to by type-~2~ or type-~3~ events.
Even if Billy manages to keep Luigi alive through all ~M~ events, he may not be out of the woods yet — his success in later challenges will depend on how much of Luigi's energy has been spent. Whenever Luigi jumps from platform ~i~ to platform ~j~, he expends ~|P_i - P_j|^K~ ~(1 \le K \le 2)~ units of energy. Note that the amount of energy required doesn't depend on the platforms' relative heights.
Help Billy determine how much energy Luigi will expend throughout all ~M~ events (if he will even survive that long). As this may amount to quite a few units of energy, you only need to determine the total modulo ~1\,000\,000\,007~.
In test cases worth ~6/39~ of the points, ~N \le 2\,000~, ~M \le 2\,000~,
and ~K = 1~.
In test cases worth another ~16/39~ of the points, ~K = 1~.
The first line of input consists of three space-separated integers, ~N~,
~M~, and ~K~.
~N~ lines follow, the ~i~-th of which consists of two space-separated integers, ~P_i~ and ~H_i~, for ~i = 1 \dots N~.
~M~ lines follow, the ~i~-th of which consists of two space-separated integers, ~E_i~ and ~X_i~, for ~i = 1 \dots M~.
Output a single integer, the total number of units of energy which Luigi
will expend (modulo ~1\,000\,000\,007~), or
-1 if he will be forced to touch
the lava and perish at any point.
Sample Input 1
5 7 1 4 4 5 5 13 6 0 8 10 8 3 1 1 4 2 1 1 -1 3 4 1 2 2 2
Sample Output 1
Sample Input 2
2 2 2 0 2 1 1 1 1 3 1
Sample Output 2
In the first case, Luigi will be forced to jump along the follow sequence of positions:
- Event 1: ~4 \to 5~
- Event 3: ~5 \to 0~
- Event 5: ~0 \to 4 \to 5 \to 10 \to 13~
- Event 7: ~13 \to 10 \to 0~
In total, these jumps require ~32~ units of energy (which is equal to ~32~ modulo ~1\,000\,000\,007~). If ~K~ were equal to ~2~ rather than ~1~, then ~186~ units of energy would be required instead.
In the second case, after the lava's height is raised to ~1.5~ metres, Luigi will have no non-submerged platform to jump to on his right, and so will be forced to jump into the lava and perish.