Calculating max from [currPos] to [currPos - k] in large array

Question

I'm preparing for ACM competition and i'm stuck with this problem.

You have buildings with given position Xi and height Hi the shields are made of steel and they need to be supported by at least two buildings with the same height. The right end of the shield must lie on top of some building. All the buildings that lie under the shield (including those that lie on the end) are protected by that shield and their height can’t exceed the height on which the shield is placed. One building can be protected with at most one shield.

You are given infinite number of shields, each with the same length L. Find the maximum number of buildings that can be protected by the shields and find the minimum number of shields that can be used to protect the maximum number of buildings.

Input

The first line of input contains one positive integer T (1 <= T <= 20), the number of test cases.

Each test case starts with a line that contains exactly two integers: the number of buildings N (2 <= N <= 100,000) and the length of a shield L (1 <= L <= 1,000,000,000). In each of the next N lines there are two integers, Xi (the position of the i-th building, 0 <= Xi <= 1,000,000,000) and Hi (the height of the i-th building, 1 <= Hi <= 1,000,000,000). The buildings are given sorted by their x coordinate. There won’t be two buildings with the same x coordinate.

Output

For each test case, on two a line, output the maximum number of buildings that can be covered and the minimum number of shields that can be used for that purpose.

Example

Input
17 3
1 2
2 1
3 2
4 3
5 1
6 2
7 4
8 2
9 3
10 4
11 2
15 2
16 1
17 3
18 3
19 1
20 2

Output
11 3

Explanation:
first shield: 1,2,3 
second shield: 7,8,9,10
third shield:  15,16,17,18

Obviously brute-force solution is easy code to code but will fail on time limit(1s), I was reading about segment tree, but since i haven't worked with segment tree i'm interested is that the way to solve this problem or is there some easier solution that i'm missing out?

P.S Although it says shield lenght is L, it's actually L+1, the last building must the highest and have a building on position [Xi-1, Xi-L] with same height to be able to place a shield and building positions will be sorted.

Answer 1

Finding the maximum from pos - k to pos is also known as "sliding window maximum problem" and it has a simple O(N) solution without segment trees or any other advanced data structures.
The algorithm is the following:
1)Let's maintain a deque of pairs <value, position>.
2)Moving the window bounds is done in the following way(I use pseudo code here):

//Moving the right border.
right <- right + 1
cur <- pair<value[right], x[right]>
while not deque.empty and deque.back.value < cur.value
    deque.pop_back()
deque.push_back(cur)

//Moving the left border.
left <- left + 1
while deque.front.position is out of [x[left], x[right]] bounds
    deque.pop_front()

3)The maximum is simply deque.front.value.

The complexity of this algorithm is O(N) because each element is pushed to the deque only once and it is removed from it only once(and each iteration of while loop in pseudo code above removes one element from the deque).

Now the solution to the original problem about the shields:
1)Let's assume dp[pos] = pair<maximum number of buildings covered, minimum number of shields used> such that all shields' right border is <= pos.
2)Let's maintain two pointers low and high. The high is a pointer to the current building and the low pointer is a pointer to the leftmost building such that x[high] - x[low] >= L.
3)high pointer is always incremented by one in the forloop and the low pointer is adjusted appropriately(to satisfy the 2) property).
4)Then dp can be computed in the following way: for a fixed value of high, dp[high] is either dp[high - 1] or dp[low - 1] + high - low + 1(the second is used only if it is possible to place a shield from low to high).
5)How to check that if it is possible to place a shield? Using the sliding window maximum algorithm, it is possible to maintain the maximum value in [low; high - 1] range and check if it is equal to H[high].
6)The answer is dp[N - 1](with 0-based indexation).

The complexity of this solution is O(N) because low and high are always incremented and they cannot be incremented more than N times and sliding window maximum algorithm complexity was shown above.