There is a city with $n$ buildings on a straight line, the $i$th building has height $h_i$.
Dr. Evil wants to destroy as many floors in these buildings as possible. To do so, he will use his devastating Super Plasma Cannon of Terror. He positioned the cannon to the left of all buildings. When he shoots at height $y$, all buildings with height at least $y$ will have their $y^{th}$ floor reduced to ashes, and all the floors with heights above $y$ will have their heights decreased one. Dr, Evil can use the cannon any number of times.
There are currently $m$ people in these buildings. The $i$ person is in building $a_i$ at height $b_i$. Since Dr. Evil is a very nice person, he decided to not kill any people in this experiment, thus he can't destroy any floor if it has at least one person.
Find the maximum number of floors Dr. Evil can destroy.
The first line of input contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5, 0 \le m \le 2 \cdot 10^5$), the number of buildings, and the number of people currently in the buildings, respectively.
The second line contains $n$ integers $h_1, h_2, ..., h_n$ ($1 \le h_i \le 2 \cdot 10^5$), the height of the buildings.
The next $m$ lines each contains two integers $a_i$ and $b_i$ ($1 \le a_i \le n, 1 \le b_i \le h_{a_i}$), the building and the floor the $i$th person is currently at, respectively.
Print a single integer, the maximum number of floors Dr. Evil can destroy.
In the first example, Dr. Evil can first fire a beam at height 2, then the second floor of both buildings will be destroyed and the person that is in building 2 at height 4 will become on a floor at height 3. Then Dr. Evil can shoot again also at height 2, which will destroy the current second floor of building 2. Now both the first and the second floors have people in them and can't be destroyed. In total, 3 floors were destroyed.
| Input | Output |
|---|---|
2 2 2 4 2 1 2 4 Copy
|
3 Copy
|
3 4 7 4 12 1 2 1 2 3 10 1 4 Copy
|
16 Copy
|
Let us assume that no floor decreases height after a floor under it is destroyed, then we should fire the cannon at every height that doesn't have any floor with people in it.
To calculate how many floors would be destroyed this way, we can create a frequency array $fr$ of heights, where $fr_i$ is the number of buildings with height $i$, we should also create a bool array $bad$, where $bad_i$ is true if there is a floor at height $i$ with people in it.
Then loop each height from $1$ to $2 \cdot 10^5$ and if $bad_i$ is false(there is no person at any floor in this height) add to the answer the number of buildings with height $ \ge i$, to get the number of such buildings for each $i$, we can keep a value $cb$ which stores the current number of buildings, at first it's equal to $n$ and after each loop we decrease the number of buildings with height $i$($fr_i$).
The solution of the original problem is exactly the above one, since all floor in the same level will always be together and no other floors will join them regardless of how we use the cannon.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
int const N = 200000;
int fr[N + 1];
bool bad[N + 1];
int main(){
int n, m;
scanf("%d%d", &n, &m);
f(i, 1, n + 1){
int h;
scanf("%d", &h);
++fr[h];
}
f(i, 0, m){
int ind, h;
scanf("%d%d", &ind, &h);
bad[h] = true;
}
ll an = 0;
int cb = n;
f(i, 1, N + 1){
if (!bad[i])an += cb;
cb -= fr[i];
}
printf("%lld\n", an);
}