Road to Home
Contest: Codeforces Round 374 (Div. 2)
Difficulty rating: 2700
Tags: binary search, dp

Once Danil the student was returning home from tram stop lately by straight road of length L. The stop is located at the point x = 0, but the Danil's home — at the point x = L. Danil goes from x = 0 to x = L with a constant speed and does not change direction of movement.

There are n street lights at the road, each of which lights some continuous segment of the road. All of the n lightened segments do not share common points.

Danil loves to sing, thus he wants to sing his favourite song over and over again during his walk. As soon as non-lightened segments of the road scare him, he sings only when he goes through the lightened segments.

Danil passes distance p while performing his favourite song once. Danil can't start another performance if the segment passed while performing is not fully lightened. Moreover, if Danil has taken a pause between two performances, he is not performing while not having passed a segment of length at least t. Formally,

1. Danil can start single performance at a point x only if every point of segment [x, x + p] is lightened;
2. If Danil has finished performing at a point x + p, then the next performance can be started only at a point y such that y = x + p or y ≥ x + p + t satisfying the statement under the point 1.

Blue half-circles denote performances. Please note that just after Danil has taken a pause in performing, he has not sang for a path of length of at least t.

Determine how many times Danil can perform his favourite song during his walk from x = 0 to x = L.

Please note that Danil does not break a single performance, thus, started singing another time, he finishes singing when having a segment of length of p passed from the performance start point.

Input format:
The first line of the input contains four integers L, n, p and t (1 ≤ L ≤ 109, 0 ≤ n ≤ 100 000, 1 ≤ p ≤ 109, 1 ≤ t ≤ 109) — the length of the Danil's path, the number of street lights at the road, the distance Danil passes while doing single performance and the minimum distance of pause respectively.

The next n lines describe segments lightened by street lights. i-th of them contains two integers li, ri (0 ≤ li < ri ≤ L) — the endpoints of the segment lightened by i-th street light. It is guaranteed that no two segments are intersecting, nesting, or touching each other. The segments are given in the order from left to right.

Output format:
Print the only integer — the maximum number of performances of Danil's favourite song on the path from x = 0 to x = L.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The first sample case is just about corresponding to the picture from the statement.

Example input:
17 2 2 6
0 9
13 17

Example output:
5

Example input:
12 2 2 2
0 5
6 11

Example output:
4

Editorial:
Firstly, if we are in some segment and we are going to sing in it, we want to sing as much as possible in this segment. So there are two cases for each segment: either we sing in the segment while we can or we just skip it.
Now we consider two different cases:
1) p ≤ 100
If we have stopped singing in the segment, then the distance we need to walk to reach the end of this segment is strictly less than p. Let's calculate two values — dpleft[i] — the answer (how many times we can sing a song) if we start from the beginning of segment number i (from li), and dpright[i][j] — the answer if we start from ri - j (0 ≤ j < p, as we already said before). To calculate the value using the value from point x, we have to find the segment which contains the point x + t and the segment which begins after this point. If we are in segment number k, we either skip it and update next segment (dpleft[k + 1]), or start singing and update the value in the point y where we stop singing (dpright[k][y]).
To find the segment containing point x + t, we can use binary search or precalculate the required indices using iterations on the array of segments.
Time complexity: $${\mathcal {O}}(np\log n)$$ or O(np).
2) p > 100
Let's use the fact that the answer is not greater than $${ \frac { L } { p } } < 1 0 ^ { 7 }$$. For each value i we calculate lfi - the leftmost point where we can get it. We will iterate on those values considering that we have already calculated lfj for every j < i when we start calculating lfi. Then if lfi is before the beginning of some segment, and lfi + 1 is after its beginning, then we can try singing starting from the beginning of this segment with i performed songs currently, updating lf for next values (from i + 1 till $$i + \left\lfloor \frac{r_k - l_k}{p} \right\rfloor$$ with the values rk - (rk - lk) mod p). Using this fact we update the value for the largest answer, skipping the points in the middle of the segment. To calculate these values we need a data structure (for example, Fenwick tree) which sustains the minimum value on the suffix (lfi is the minimum on suffix beginning from element number i). All lf values are increasing, so we need only one variable to sustain the index of the segment we are using to update.
How we have to consider the points in the middle of some segment. So we have a variable storing the index of the rightmost segment which begins before lfi for current answer i. It may seem that the values from the beginning and from the middle of some segment may be used in the wrong order, but it's easy to prove that it's not true.
Copmplexity: $$O\left(\frac{L}{p}\log\left(\frac{L}{p}\right)+n\right)$$. We can use a special updating structure based on stack to get rid of Fenwick tree, then complexity will be $${\mathcal{O}}\left({\frac{L}{p}}+n\right)$$.