3435 . [模板題] Segment Add Get Min
TopCoder
Tags
Description
There are $N$ segments $y = a_ i x + b_ i$ (where $x \in [l_ i, r_ i)$). Process $Q$ queries.
0 l r a b: Add a segment $y = ax + b$ (where $x \in [l, r)$)1 p: Find the minimal $y$ at $x = p$. If such $y$ doesn't exist, outputINFINITY.
Input Format
$N$ $Q$
$l_ 0$ $r_ 0$ $a_ 0$ $b_ 0$
$l_ 1$ $r_ 1$ $a_ 1$ $b_ 1$
:
$l_ {N-1}$ $r_ {N-1}$ $a_ {N-1}$ $b_ {N-1}$
$\textrm{Query}_ 0$
$\textrm{Query}_ 1$
:
$\textrm{Query}_ {Q - 1}$
Output Format
Sample Input 1
2 8 -3 3 -1 -1 0 7 0 1 1 -1 1 -2 1 0 1 2 0 -4 2 0 -10 1 -2 1 0 1 2
Sample Output 1
0 1 -1 -3 -10 -10 -3
Sample Input 2
1 2 -10 0 0 0 1 0 1 -1
Sample Output 2
INFINITY 0
Hints
- $1 \leq N, Q \leq 2 \times 10^ {5}$
- $-10^ {9} \leq l_ i \lt r_ i \leq 10^ {9}$
- $|a_ i|, |p| \leq 10^ {9}$
- $|b_ i| \leq 10^ {18}$
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|