3435 . [模板題] Segment Add Get Min

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

66.7% (2/3)

Tags

library-checker template

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.

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

library checker: segment_add_get_min

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 2097152 2097152
1 5000 2097152 2097152
2 5000 2097152 2097152
3 5000 2097152 2097152
4 5000 2097152 2097152
5 5000 2097152 2097152
6 5000 2097152 2097152
7 5000 2097152 2097152
8 5000 2097152 2097152
9 5000 2097152 2097152
10 5000 2097152 2097152
11 5000 2097152 2097152
Submit
Back to Top