stopping_by_woods's blog

By stopping_by_woods, history, 4 years ago, In English

Can someone plz explain how to do this problem. Problem from the recent hackerearth contest

You are given n ($$$1$$$ $$$\le$$$ $$$n$$$ $$$\le$$$ $$$300000$$$) queries. Each query is one of $$$3$$$ types:

  1. add pair ($$$a$$$, $$$b$$$) to the set. ($$$-10^9$$$ $$$\le$$$ $$$a, b$$$ $$$\le$$$ $$$10^9$$$)

  2. remove a pair added in query $$$index$$$ (All queries are numbered with integers from $$$1$$$ to $$$n$$$).

  3. For a given integer $$$A$$$ find the maximal value $$$a·A + b$$$ over all pairs ($$$a$$$, $$$b$$$) from the set. ($$$-10^9$$$ $$$\le$$$ $$$A$$$ $$$\le$$$ $$$10^9$$$). It is guaranteed that the set of pair will not be empty.

INPUT.

The first line contains integer $$$n$$$ ($$$1$$$ $$$\le$$$ $$$n$$$ $$$\le$$$ $$$3·10^5$$$) — the number of queries.

Each of next $$$n$$$ lines starts with integer $$$op$$$ ($$$1$$$ $$$\le$$$ $$$op$$$ $$$\le$$$ $$$3$$$) — the type of query.

OUTPUT

For each query of $$$3$$$ type print on a separate line the maximal value of $$$a·A + b$$$. It is guaranteed that the set of pair will not be empty.

Full text and comments »

By stopping_by_woods, history, 4 years ago, In English

Problem Link

Can someone help how to do this problem. The editorial is a bit unclear to me. I am finding it difficult to make transitions between the dp states. Thanks in advance!

Full text and comments »