8842: [yosupo] Data Structure - Segment Add Get Min
[Creator : ]
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, output `INFINITY`.
- 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, output `INFINITY`.
Input
$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}$
$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}$
Constraints
$1 \leq N, Q \leq 200,000$
$-10^9 \leq l_i \lt r_i \leq 10^9$
$|a_i|, |p| \leq 10^9$
$|b_i| \leq 10^{18}$
$-10^9 \leq l_i \lt r_i \leq 10^9$
$|a_i|, |p| \leq 10^9$
$|b_i| \leq 10^{18}$
Sample 1 Input
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 1 Output
0
1
-1
-3
-10
-10
-3
Sample 2 Input
1 2
-10 0 0 0
1 0
1 -1
Sample 2 Output
INFINITY
0