1
\$\begingroup\$

Input

You are given 2 positive integers, n, q, followed by q queries. the queries can be of two forms:

  • 0 a b: add the line a*x + b. a and b are integers between -10^9 and 10^9 inclusive.
  • 1 x: output the minimum of all the lines evaluated at x, x being an integer between 0 and n inclusive

Example

Input:

100 9
0 10 5
1 50
0 9 10
1 49
1 4
0 5 408
1 99
1 100
1 0

Output:

505     (10*50+5=505)
451     (10*49+5=495, 9*49+10=451)
45      (10*4+5=45, 9*4+10=46)
901     (10*99+5=995, 9*99+10=901, 5*99+408=903)
908     (10*100+5=1005, 9*100+10=910, 5*100+408=908)
5       (10*0+5=5, 9*0+10=10, 5*0+408=408)

Restrictions

Your code must run in \$O(q\log^2(n)+n\log^2(n))\$ time or better.

Extra

First query will allways be of type 0.

The bounds on a and b are also considered a factor of time the complexity if used, 10^9 was chosen to fit within 32 bit integers.

Score

The answer with the shortest code, in bytes wins.

Non-golfed example solution in Python 3

n, q = map(int, input().split())

class line:
    def __init__(self, a, b):
        self.a = a
        self.b = b
    def evaluate(self, x):
        return self.a*x + self.b

inf = float('inf')
LCT = [line(inf, inf)]*(n + 1) #initialise Li Chao Tree

def insert_line(line, left = 0, right = n):
    mid = (left + right)//2
    if line.evaluate(mid) < LCT[mid].evaluate(mid):
        #if the line being inserted is minimal, swap
        LCT[mid], line = line, LCT[mid]
    if left != right:
        #if the bottom of the tree hasn't been reached:
        if line.a < LCT[mid].a:
            #intersection will be to the right
            insert_line(line, mid + 1, right)
        else:
            #intersection will be to the left
            insert_line(line, left, mid)

def find_minimum(x, left = 0, right = n):
    mid = (left + right)//2
    low = LCT[mid].evaluate(x) #store minimal found line
    if left != right:
        if x > mid:
            #search right
            low = min(low, find_minimum(x, mid + 1, right))
        else:
            #search left
            low = min(low, find_minimum(x, left, mid))
    return low

for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 0:
        insert_line(line(query[1],query[2]))
    else:
        print(find_minimum(query[1]))
```
Improve this question
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Please consider using the sandbox before posting to the main site. Also, quickly answering your own challenge is frowned upon. You should wait at least 1 week. (Alternatively, you can include an ungolfed example implementation in the question itself.) \$\endgroup\$ Commented Mar 17 at 11:11
  • \$\begingroup\$ @Arnauld thanks, I don't know the culture here. when I previously included an example someone complained as well, will remove my solution for a week though, thanks \$\endgroup\$ Commented Mar 17 at 13:41
  • 1
    \$\begingroup\$ I edited your challenge to make it look a bit better. Let me know if I missed anything. \$\endgroup\$ Commented Mar 17 at 17:04
  • 1
    \$\begingroup\$ It seems to me that the restriction that \$|a|\le10^9\$ and \$|b|\le10^9\$ means that I can ignore a 0 a b line if it has already appeared before. Only a constant number of lines, so adding a line takes constant time. For comparing values, there are at most \$(2\times10^9+1)^2\$ lines to compare, so at most that many multiplications and additions, which can be done in time logarithmic in \$n\$. \$\endgroup\$ Commented Mar 18 at 0:54
  • \$\begingroup\$ @Lucenaposition the bounds on a and b was to make it solvable with 32 bit integers, not to make the amount of lines bounded, I will add a clarification \$\endgroup\$ Commented Mar 18 at 10:22

2 Answers 2

Reset to default
1
\$\begingroup\$

Python3 378 bytes

I=lambda:map(int,input().split())
n,q=I()
def h(a,b):
 def f(x):return a if x<0 else a*x+b
 return f
L=[h(1e9,1e9)]*-~n
def m(p,l=0,r=n):
 k=l+r>>1;v=L[k](p)
 if l<r:v=min(v,m(p,k+1,r)if p>k else m(p,l,k))
 return v
def i(f,l=0,r=n):
 k=l+r>>1
 if f(k)<L[k](k):L[k],f=f,L[k]
 l>=r or(f(-1)>L[k](-1)or i(f,k+1,r))and i(f,l,k)
while q:q-=1;t,*x=I();(t or i(h(*x)))and print(m(*x))

h returns a line given a, b, returns a if x<0

i inserts a line into a LCT in O(logn) time

m returns the minimum at p in O(logn) time

last line is the control segment, controlling whether i or m should be called

time complexity: O(qlogn+n)

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python, 116 bytes

A={};I=int;input()
while x:=input().split():
 if I(x[0]):print(min(I(x[1])*I(a)+I(b)for a,b in A))
 else:A[*x[1:]]=1

Attempt This Online!

The integers a and b are bounded in size, so there is a maximum size for the dict (at most \$(2\times10^9+1)^2\$). This means the iterator in the third line has a bounded size. The multiplication and addition takes time logarithmic in \$n\$ (as x[1] is at most n for line 3) and there are at most \$q\$ such times where we have to multiply and add. The dict having a bounded size means the time for a dict insertion (in line 4) is constant. This means the total time is \$O(q\log(n))\$.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ bounds of a and b are now also used for time complexity calculation, your time complexity is now \$O(ABq\log(n))\$ I appreciate the technically correct answer though, the best kind of correct \$\endgroup\$ Commented Mar 18 at 10:44
  • \$\begingroup\$ should I delete or keep my answer? \$\endgroup\$ Commented Mar 18 at 22:57
  • \$\begingroup\$ you can keep it, it's a fun one \$\endgroup\$ Commented Mar 19 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.