PEG Test - Halloween 2014
Kenny wants to go trick-or-treating too! But the street has many spooky decorations put up on it. Kenny doesn't like to be scared, so he avoids spooky areas.
There are houses arranged in a line on the street, numbered from to . Each house will give exactly unit of candy to Kenny. There are spooky decorations on this street. The -th decoration covers the street from house number to , inclusive, raising the spookiness of those houses by spookiness units.
Kenny will be too scared to knock on any doors if the spookiness of a house is greater than or equal to . The spookiness of a house is the sum of the spookinesses of all the decorations passing through it.
Determine the amount of candy Kenny can receive from all the houses on the street.
The first line of input will contain the integers: , ,
The next lines of input will contain values , and for each house. .
Output a single integer, the amount of candy that Kenny can get.
Sample Input 1
3 100 10 20 59 4 30 69 4 40 79 4
Sample Output 1
Houses between number 40 and 59 inclusive have a spookiness of 12, which is 2spooky for Kenny. He can still get candy from houses 1 to 39, and 60 to 100.
Sample Input 2
2 10 4 3 5 2 5 7 2
Sample Output 2
Only house 5 is 2spooky for Kenny.
May I ask if this is solvable by Fenwick? Isn't 10^9 too much?
You could try coordinate compressing it