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++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, 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

?