Problem D
Streaming Statistics
When delivering streaming music one keeps track of which track was requested, when streaming completed (Unix epoch in milliseconds (ms)), its duration in milliseconds (ms), and its bitrate in kilobits per second (kbps). If a track has duration 100 000 ms and ended at 1325967178930, that means it started at 1325967078930 and played until 1325967178930. If its bitrate was 96 kbps then the amount ofa data streamed due to this song was 9 600 kb. During the interval between 1325967078930 and 1325967078931, 96 bits was streamed, and during the interval between 1325967178930 and 1325967178931 nothing was streamed (as it stopped at 1325967178930). Veronica tells Eddie he can make the assumption that start and stop times are exact, and also that at bitrate $r$ kbps, exactly $r$ bits are sent every millisecond (in reality data would be sent in “bursts” as larger packages).
Eddie’s task is to analyze a simplified log file. The log file is a sequence of lines, each of which has three numbers, $t, d, r$ which are the end time (Unix epoch in ms), duration (ms) and bitrate (kbps) of a track.
The log file entries are followed by a number of queries. Each query is a pair of times (Unix epochs in ms), $a,b$ where $a\leq b$. You should output the total amount of data streamed between times $a$ and $b$, in kilobits (kb).
Eddie, feeling he is in over his head, has retained you as a consultant to do the actual analysis of the log files.
Input
The first line consists of an integer $N$, $1\leq N\leq 100\, 000$ which is the number of log entries. The following lines contain integer log entries $t_ i\ d_ i\ r_ i$ as described above.
The log entries are followed by a line with a single integer $Q$, $1\leq Q\leq 100\, 000$ which is the number of queries. The following $Q$ lines contain time intervals $a_ j\ b_ j$ as described above.
You may assume that $1\, 325\, 000\, 000\, 000 \leq t_ i, a_ j, b_ j \leq 1\, 326\, 000\, 000\, 000$, $0 \leq d_ i\leq 30\, 000\, 000$, $1\, 325\, 000\, 000\, 000 \leq t_ i-d_ i$, and $64\leq r_ i\leq 320$
Output
For each of the $Q$ queries $a_ j\ b_ j$, output a line containing the total amount (in kb) streamed during the time interval, rounded to exactly three decimals.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 1325338338022 320412 160 1325338361231 441201 320 1325338341231 474123 96 1325338312302 234123 312 1325338331141 623132 147 5 1325300000000 1325400000000 1325338300000 1325338500000 1325338336412 1325338339612 1325338312302 1325338341231 1325338320000 1325338340000 |
402612.828 38051.567 1588.800 18918.997 12841.247 |
