Back To School '16: Textbooks

View as PDF
Submit solution
Points: 20 (partial)
Time limit: 4.5s
Memory limit: 256M
Author:
aurpine
Problem type

bobhob314 has applied some super sticky substance to his N textbooks. This mysterious substance is so sticky that it prevents textbooks from falling off ledges in a Tetris-like manner. The n^\text{th} textbook is placed starting at s_n and is l_n units long and w_n wide. The textbooks are given in the order in which they are placed.

The sun is shining directly above and bobhob314 wants to protect more books from the sun. Find the total area unoccupied by a textbook in the shade (has at least one part of a textbook above). Print this modulo 1\,000\,000\,007.

Input Specification

The first line contains a single integer N.

The next N lines contain 3 space separated integers, s_n, l_n and w_n.

Note: fast input may be required.

Constraints

Subtask 1 [10%]

1 \le N \le 100

1 \le s_n, l_n \le 100\,000

w_n = 1

Subtask 2 [30%]

1 \le N \le 10\,000

1 \le s_n, l_n \le 10^9

1 \le w_n \le 10

Subtask 3 [60%]

1 \le N \le 500\,000

1 \le s_n, l_n \le 10^9

1 \le w_n \le 100

Output Specification

Output a single integer, the number of empty spaces under at least one textbook modulo 1\,000\,000\,007.

Sample Input 1

3
1 3 1
3 3 1
5 3 1

Sample Output 1

6

Sample Input 2

5
1 2 1
3 1 1
3 4 1
6 3 2
5 2 1

Sample Output 2

9

Explanation for Sample Output 2

The textbooks are represented with a digit. A period represents a unit in the shade.

    55
    .444
    .444
  3333..
112.....

Sample Input 3

4
5 1 2
3 1 2
5 1 1
3 3 1

Sample Output 3

4

Explanation for Sample Output 3

  444
  ..3
  2.1
  2.1

Comments


  • 23
    Paradox  commented on Sept. 17, 2016, 1:08 a.m. ← edit 2

    bobhob314 and his super sticky substance ( ͡° ͜ʖ ͡°)---->Suspicious.


    • 19
      bobhob314  commented on Sept. 17, 2016, 8:27 p.m.

      :(