All Tracks Data Structures Advanced Data Structures Problem

Points on line
Tag(s):

Data Structures, Medium-Hard

Problem
Editorial
Analytics

This task is really interesting so authors even decided not to spend your time on reading the statement!

Initially you have a straight line without any points on it and you need to perform three types of queries:

1 $$x$$ - add a point with an integer coordinate $$x$$. Guaranteed that there is no such point before running this query.

2 $$x$$ - delete a point with an integer coordinate $$x$$. Guaranteed that this point exists before running this query.

3 $$x$$ - define a coordinate of i-th existing point in increasing order as $$x_i$$ and number of existing points as $$n$$. You need to find $$max ( \sum_{i=1}^{n-1} |x_{p_{i+1}} - x_{p_i}| )$$ for all permutations $$p$$ of length $$n$$ where $$x_{p_1}=x$$. Guaranteed that this point exists before running this query.

Input
The first line of input contains a single integer $$q$$ $$(1 \leq q \leq 100 000)$$ - the number of queries.

Then follow $$q$$ lines. The i-th of these lines contains two integers $$type_i$$ and $$x_i$$ $$(1 \leq type_i \leq 3, 0 \leq x_i \leq 10^{9})$$.

Output
For each query of the third type print the maximum value.

SAMPLE INPUT
7
1 0
1 5
1 4
1 3
3 4
2 5
3 4
SAMPLE OUTPUT
11
7
Explanation

Permutation for the first ask query is {3, 1, 4, 2}. It's value is 11.

Permutation for the second ask query is {3, 1, 2}. It's value is 7.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HackerEarth Collegiate Cup - Mirror Round

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications