2spooky4me

View as PDF
Submit solution
Points: 7
Time limit: 1.0s
Memory limit: 16M
Authors:
Alex, frenzybenzy
Problem type
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 L houses arranged in a line on the street, numbered from 1 to L. Each house will give exactly 1 unit of candy to Kenny. There are N spooky decorations on this street. The i-th decoration covers the street from house number a_i to b_i, inclusive, raising the spookiness of those houses by s_i spookiness units.

Kenny will be too scared to knock on any doors if the spookiness of a house is greater than or equal to S. 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.

Input Specification

The first line of input will contain the integers: N, L, S (1 \le N \le 10\,000; 1 \le L \le 10^9; 1 \le S \le 10^7).
The next N lines of input will contain values a, b and s for each house. (1 \le a_i, b_i \le L; 1 \le s_i \le 1\,000).

Output Specification

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

80

Explanation 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

9

Explanation 2

Only house 5 is 2spooky for Kenny.

Comments


  • 2
    Pimienta  commented on Aug. 28, 2021, 8:08 p.m. ← edit 2

    May I ask if this is solvable by Fenwick? Isn't 10^9 too much?


    • 6
      LeonLiur  commented on Dec. 18, 2021, 7:19 p.m.

      You could try coordinate compressing it