WC '18 Contest 4 S4 - Super Luigi Odyssey

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 3.0s
Memory limit: 128M

Problem type
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.

Input Specification

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 Specification

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


Sample Explanation

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.


There are no comments at the moment.