### PROBLEM LINK:

**Author:** [Abhinav Jain]

**Tester:** Michael Nematollahi

**Editorialist:** Hussain Kara Fallah

### DIFFICULTY:

Easy-Medium

### PREREQUISITES:

None

### PROBLEM:

You have C=100,000 cakes, numbered 1 through C. Each cake has an integer height. Initially, the height of each cake is 0. There are Q operations. In each operation, you are given two integers L and R and you should increase by 1 the height of all cakes at positions [L,L+1,…,R].

One of these Q operations should be removed and the remaining Q−1 operations are then performed. Given K, help chef by finding one operation to remove such that after performing remaining operations the number of cakes with a height of exactly K is maximum possible.

### EXPLANATION:

We will discuss a linear solution to this problem. Let’s first assume that all operations are performed. How can we calculate cakes’ heights after all operations are finished?

Let’s read all the operations first. Then, let’s iterate through cakes from the first one till the last one. Suppose that we are processing currently the i_{th} cake. If there is some operation which has L=i that means that we must increase the heights of all cakes while we are moving forward until R+1=i. When R+1=i that mentioned operation won’t affect any more cakes.

So we should keep an array change[1\,...\,C].

change_i denotes the number of queries with L=i minus the number of queries with R=i-1.

(R=i-1 because the R_{th} cake should be incremented and the increment must be canceled at R+1).

So how to calculate the final heights? (Think a little bit).

```
for(int i = 1 ; i ≤ C ; i++)
height[i] = height[i-1] + change[i];
```

Simple !!

Now which query we should remove?

Let’s think about the outcome of removing one operation and canceling its effects. All cakes between the L_{th} and the R_{th} (inclusive) will have their heights decreased by 1. So after removing a certain operation, the number of cakes with height K is equal to A+B+C

**A** = number of cakes with a height equal to exactly K between the 1^{st} cake and the (L-1)^{th} cake

**B** = number of cakes with a height equal to exactly K+1 between the L^{th} cake and the R^{th} cake

**C** = number of cakes with a height equal to exactly K between the (R+1)^{th} cake and the last cake.

So after calculating the heights resulting from applying the operations, we are interested in only 2 heights. K and (K+1).

Keep 2 prefix sum arrays, target[1\,...\,C] , targetplus[1\,...,C]

target_i denotes the number of cakes with final height equal to K among the first i cakes.

targetplus_i denotes the number of cakes with final height equal to K+1 among the first i cakes.

Now, it’s easy to check each operation and check the effect of removal and update our answer accordingly. Check codes for more details.

Complexity O(N + Q)