Minecraft Series
Contest: Codeforces Round 829 (Div. 1)
Difficulty rating: 3500
Tags: brute force, two pointers

Little Misha goes to the programming club and solves nothing there. It may seem strange, but when you find out that Misha is filming a Minecraft series, everything will fall into place...

Misha is inspired by Manhattan, so he built a city in Minecraft that can be imagined as a table of size $$$n \times m$$$. $$$k$$$ students live in a city, the $$$i$$$-th student lives in the house, located at the intersection of the $$$x_i$$$-th row and the $$$y_i$$$-th column. Also, each student has a degree of his aggressiveness $$$w_i$$$. Since the city turned out to be very large, Misha decided to territorially limit the actions of his series to some square $$$s$$$, which sides are parallel to the coordinate axes. The length of the side of the square should be an integer from $$$1$$$ to $$$\min(n, m)$$$ cells.

According to the plot, the main hero will come to the city and accidentally fall into the square $$$s$$$. Possessing a unique degree of aggressiveness $$$0$$$, he will be able to show his leadership qualities and assemble a team of calm, moderate and aggressive students.

In order for the assembled team to be versatile and close-knit, degrees of aggressiveness of all students of the team must be pairwise distinct and must form a single segment of consecutive integers. Formally, if there exist students with degrees of aggressiveness $$$l, l+1, \ldots, -1, 1, \ldots, r-1, r$$$ inside the square $$$s$$$, where $$$l \le 0 \le r$$$, the main hero will be able to form a team of $$$r-l+1$$$ people (of course, he is included in this team).

Notice, that it is not required to take all students from square $$$s$$$ to the team.

Misha thinks that the team should consist of at least $$$t$$$ people. That is why he is interested, how many squares are there in the table in which the main hero will be able to form a team of at least $$$t$$$ people. Help him to calculate this.

Input format:
The first line contains four integers $$$n$$$, $$$m$$$, $$$k$$$ and $$$t$$$ ($$$1 \le n, m \le 40\,000$$$, $$$1 \le n \cdot m \le 40\,000$$$, $$$1 \le k \le 10^6$$$, $$$1 \le t \le k + 1$$$) — the number of rows and columns in the table, and the number of students living in the city, respectively.

Each of the following $$$k$$$ lines contains three integers $$$x_i$$$, $$$y_i$$$ and $$$w_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$, $$$1 \le \lvert w_i \rvert \le 10^9$$$) — the number of row and column, where the $$$i$$$-th student is living, and the degree of his aggressiveness.

Output format:
Print one integer — the number of ways to choose the square $$$s$$$ in such way that the main hero will be able to form a team of at least $$$t$$$ people.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Note:
1. In the first example the main hero will not be able to form a team of more than one person in any square $$$s$$$.   Illustration for the first example.
2. In the second example there are two ways to select square $$$s$$$. Both of them are illustrated below. In one of them the main hero will be able to form a team of students with degrees of aggressiveness $$$[0, 1]$$$, and in the another — with degrees of aggressiveness $$$[0, 1, 2]$$$. Notice, that the main hero with degree of aggressiveness $$$0$$$ will be included to the team regardless of the chosen square.   Illustration for the second example.
3. In the third example there are four ways to select square $$$s$$$. All of them are illustrated below. The main hero will be able to form a team with degrees of aggressiveness: $$$[-1,0,1]$$$, $$$[0,1]$$$, $$$[0,1]$$$, $$$[-1, 0, 1]$$$, respectively.   Illustration for the third example.

Example input:
2 2 1 2
1 1 2

Example output:
0

Example input:
2 2 2 2
1 1 1
2 2 2

Example output:
2

Editorial:
Let's formalize the problem condition. It is required to calculate the number of squares $$$s$$$ in the table for which we have inequality $$$A+B \geq T$$$, where $$$A$$$ is a $$$\text{MEX}$$$ of positive integers in the sqare and $$$B$$$ is a $$$\text{MEX}$$$ of absolute values of all negative integers in the square. Then we denote cost of a square as $$$A+B$$$. Note that when the square is expanded, its value cannot decrease.
Let's fix the diagonal that contains the upper left and lower right sides of the square. Now, with a fixed lower right cell, we want to maintain the upper left cell of the square that is maximally removed from it so that its cost does not exceed $$$T-1$$$. Note that this upper-left boundary can only shift in the direction of moving the right lower one, which means we can use the two pointers technique.
We will also need to maintain a set of numbers that are contained in a square. To do this, we will process each cell separately, which are added and removed from our square. Note that for each cell there are no more than $$$\min \{ N, M \}$$$ diagonals on which it is possible to construct a square containing this cell, and also note that due to the structure of our solution for each such diagonal, our cell will be added to the set no more than $$$1$$$ time. Thus, the total number of additions of cells to our set does not exceed $$$M N \cdot \min \{N, M \}$$$, and accordingly the total number of additions of numbers to the set does not exceed $$$K \cdot \min \{ N, M \}$$$.
We will also need to find out the $$$\text{MEX}$$$ of all positive integers in the square, as well as the $$$\text{MEX}$$$ of absolute values of negative integers in the square. Here we need to make another observation about our algorithm. The number of $$$\text{MEX}$$$ queries will not exceed $$$2MN$$$. That is, you can use the square roots technique to adding and removing integers in $$$O(1)$$$ time, and find out the $$$\text{MEX}$$$ values in $$$O(\sqrt K)$$$ time.
To summarize, our algorithm will work in asymptotic time:
$$$$$$ O((NM + K) \cdot \min \{ N, M \} + NM \sqrt{K}) $$$$$$
As the author of the problem, I want to apologize for the very low TL in this problem. Due to the specificity of the task, it was difficult to cut off the wrong solutions. The solution described above, if implemented correctly, fits into TL with a time reserve at least $$$1$$$ second. But if suddenly you didn't write it efficiently enough and you have TL, then you can try using the following tips:
• Sort the numbers in each cell. This will help to better in the cache. It does benefit buffering provided by a cache.
• It is more accurate to implement your algorithm without making unnecessary MEX queries.
• Use bit magic and implement the $$$\text{MEX}$$$ search in $$$O(\omega + K/\omega)$$$ time where $$$w=64$$$ is machine word size. Such a solution may have a better time-constant and it is better to be vectorized