TREAP - Yet another range difference query!
Given an empty set S, you have to apply Q operations on this set while keeping the set sorted in increasing order and elements have indices 0 <= i < size(S)
The operations are insert, delete, find min difference in a given range, find max difference in a given range.
Input
I k : Insert k into S, if k is not in S
D k : Delete k from S, if k is in S
N i j : Print min{abs(S[x] - S[y]) | i <= x, y <= j} or -1 if the range has 1 element
X i j : Print max{abs(S[x] - S[y]) | i <= x, y <= j} or -1 if the range has 1 element
limits: 0 < Q <= 200000 , 0 <= k <= 10^9 , 0 <= i,j < size(S)
Output
For each N and X operations, print an integer per line as described above.
Example
Input: 11 I 1 I 12 I 4 I 8 N 0 3 X 0 3 N 1 3 X 0 2 D 4 N 0 1 X 1 2 Output: 3 11 4 7 7 4
hide comments
jusbut1943:
2018-08-31 11:16:01
Why my solution is black, and shows 0K, Result: 0. |
|
fz0718:
2017-07-22 23:10:28
Another fun BBST problem, that you also need lazy propagation for: https://csacademy.com/contest/archive/task/strings/ |
|
mahmud2690:
2016-05-25 13:30:54
Why my solution is black, and shows 0K, Result: 0. |
|
timonknigge:
2015-08-31 15:20:40
It might be worth pointing out that for the N query, we also require that x =/= y. |
|
bicsi:
2015-07-02 23:38:35
This was probably the most resourceful problem I have ever coded! However, it was worth it in the end! :D |
Added by: | ahmed.abdrabo |
Date: | 2013-04-22 |
Time limit: | 5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | modified zeap from infoarena.ro |