we are provided with n different range(l,r) and each range have value (val) associated with it . now we have given k query , in each query we have given one integer X , and we have to tell the minimum value we can obtain form the ranges in which X
lies i.e L<=x<=R , if their does not exist any range print -1 .
Input :
n — number of range .
next n line contain — ( l , r , val )
q — number of query.
next q line contain — (X)
output :
q — line with minimum value.
For Example:
Input:
4
0 0 2
0 2 10
5 6 13
1 1 2
6
0
1
2
3
5
8
Output:
2
2
10
-1
13
-1
Auto comment: topic has been updated by ultranoobs (previous revision, new revision, compare).
Constraints?
1 <= l,r <= 1e9
1<=n,q<= 2e5
There is a simple segment tree solution for this problem. The problem is just a range update and point query problem. You have an array, initially all elements are infinity. You are given some ranges and values, you have to update them and keep the minimum value. And for query, you have to output the minimum element we can get in the $$$xth$$$ element.Here the main problem is, $$$L,R \leq 10^{9}$$$. So we need to use an Implicit Segment Tree.
It's easy to show that the update complexity is $$$O(\log n)$$$ and the query complexity is also $$$O(\log n)$$$. So you have overall $$$O(n \log n+q \log n)$$$ complexity which is enough.
And you also need $$$O(n \log n)$$$ memory, which is not so much for $$$n = 10^5$$$
I think coordinate compression can be use in place of implicit segment tree
Master_coder yes, you are right, it's easily possible.
1) Sort all ranges by L, and then by R
2) Sort queries by X (we gonna do this offline)
3) Keep two pointers on the ranges you just sorted (ptL, ptR) and keep the tuple of ranges in a set<tuple<int, int, int>> (first value = val, second value = L, third value = R). Let's also define a good range [L, R] is where x is in that range.
4) For each X: move ptR forward to the point it finds the last good range, move ptL forward to the point it finds the first good range (Add every good range to the set, and remove every bad range from the set).
5) use set.first() to get the min value
6) Go to 4
I'm gonna leave it as an exercise to you to find prove the correctness of this algorithm, as well as processing the odd cases while moving the pointers to print -1.
Edit: Mandatory complexity analysis by steps:
1 and 2) O(n log n + q log q) with sorting
the rest) O(n log n + q) because you are using set operations (O(log n)) inside the two pointers technique (O(n)). The additional "q" is just because you are processing the queries.