Back to School '16: Textbooks

View as PDF

Submit solution


Points:20 (partial)
Time limit:10.0s
Memory limit:256M
Author:

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 nth 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 n. 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


  • 2
    thomas0115
     commented on Sept. 17, 2016, 11:46 p.m.
    Test Data

    If I'm not mistaken, test case 9 in subtask 1 has s>100 000 or l>100 000.


    • 3
      aurpine
       commented on Sept. 18, 2016, 10:34 a.m. edit 2

      The test cases have been fixed


  • 5
    Paradox
     commented on Sept. 16, 2016, 9:08 p.m. edit 2
    *sigh*

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


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

      :(