Back To School '16: Textbooks

View as PDF

Submit solution

All submissions

Best submissions

Points: 20 (partial)

Time limit: 4.5s

Memory limit: 256M

Author:

aurpine

Problem type

bobhob314 has applied some super sticky substance to his $N$ $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}$ $n^{th}$ textbook is placed starting at $s_n$ $s_{n}$ and is $l_n$ $l_{n}$ units long and $w_n$ $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$ $1 000 000 007$ .

Input Specification

The first line contains a single integer $N$ $N$ .

The next $N$ $N$ lines contain $3$ $3$ space separated integers, $s_n$ $s_{n}$ , $l_n$ $l_{n}$ and $w_n$ $w_{n}$ .

Note: fast input may be required.

Constraints

Subtask 1 [10%]

$1 \le N \le 100$ $1 \leq N \leq 100$

$1 \le s_n, l_n \le 100\,000$ $1 \leq s_{n}, l_{n} \leq 100 000$

$w_n = 1$ $w_{n} = 1$

Subtask 2 [30%]

$1 \le N \le 10\,000$ $1 \leq N \leq 10 000$

$1 \le s_n, l_n \le 10^9$ $1 \leq s_{n}, l_{n} \leq 10^{9}$

$1 \le w_n \le 10$ $1 \leq w_{n} \leq 10$

Subtask 3 [60%]

$1 \le N \le 500\,000$ $1 \leq N \leq 500 000$

$1 \le s_n, l_n \le 10^9$ $1 \leq s_{n}, l_{n} \leq 10^{9}$

$1 \le w_n \le 100$ $1 \leq w_{n} \leq 100$

Output Specification

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

Sample Input 1

Copy

Sample Output 1

Copy

Sample Input 2

Copy

Sample Output 2

Copy

Explanation for Sample Output 2

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

Copy

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

Sample Input 3

Copy

Sample Output 3

Copy

Explanation for Sample Output 3

Copy

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.

:(