### PROBLEM LINK:

**Author:** Anudeep Nekkanti

**Tester:** Minako Kojima

**Editorialist:** Lalit Kundu

### DIFFICULTY:

MEDIUM

### PRE-REQUISITES:

Binary Search, Basic math, Data Structures

### PROBLEM:

You have **N** rectangles of sides **L _{i}, B_{i}**. You can move them and place them anywhere, but you cannot rotate them. You can also remove

**M**of those rectangles. Finally we take the intersection of left rectangles. What is the maximum possible intersection area.

**N**≤ 10

^{5}.

### QUICK EXPLANATION:

- Use binary search on area.
- Sort pair of
**(L_i,B_i)**. In each step from**i=0 to M**, consider to remove first**i**rectangles. After removing first**i**rectangles, we can delete**M - i**more smallest breadths from available rectangles and we’ll get the maximum area.

### EXPLANATION:

One of the most basic things is that we’ll keep left bottom vertices of all rectangles are origin. For example in a way like this(different colors represent different rectangles):

This will always give us the maximum intersection area possible. It is a very intuitive result, however we can think like if we increase y-coordinate of any rectangle(keeping everyone else at origin) it’ll never cause us profit.

First of all let’s find intersection area if we can’t remove any rectangle:

It’s **min(L _{i}) * min(B_{i})**. (Length and breadth of intersection can’t exceed the min length and min breadth).

Now that we can remove **M** rectangles, we will be able to achieve better results since we can increase minimum of lengths and breadths.

### APPROACH1:

An interesting thing to note here will be that if our answer area is **A**(ie. most optimal solution), any area less than **A** will also be possible. So, we can do binary search here. For binary search, we’ll have to check if an area **A** is possible to achieve by deleting atmost **M** rectangles.

To check if an area **A** is possible, we traverse over all rectangles and do the following process:

Assuming **L _{i}** is the minimum length after deletions. So, all rectangles that wouldn’t have been deleted would have length greater than

**L**. Also, since we are achieving area

_{i}**A**, all remaining rectangles will have breadth atleast

**A/(B**. Let’s say

_{i})**K**is number of rectangles

**j**where

**L**and

_{j}≤ L_{i}**B**. If

_{j}≤ A/(B_{i})**K ≤ M**(ie. we have deleted atmost

**M**rectangles), it’s possible to achieve this area.

So, we have a list of pairs **(x_i, y_i)** and for a given **i**, we query: find number of pairs **j** such that **x_j ≤ x_i** and **y_j ≤ (A/y_i)**. We’ll need to do this for all **i**. The order in which we do such queries is **not** important here.

So, we sort the list of pairs first. How does this help?

Choosing the index **i** in new sorted list means that all pairs with index greater than **i** are straightaway excluded from scrutiny(because their **x** is surely greater than **x_i**). And now we need to count number of possible **j ≤ i**, such that **y_j ≤ (A/y_i)**. For this we can use a BIT. While going in increasing order of **i**, we keep marking the positions of **y_j** in the BIT and then we can count number of **y_j** less than **A/y_i**. But for that we’ll need to use coordinate compression(because **x_i, y_i** are less than 10^{9}). Coordinate compression basically means mapping larger values to smallers values(because there are only 2*N distinct values of **x_i** and **y_i**).

Complexity here would be **O(log(A) * N * log MAX)**. where **MAX = 2*N** and **A = 10 ^{18}** in worst case.

### AN EASIER APPROACH:

An easier approach would be to fix the answer as **L * B**, we then need to remove all rectangles whose **L _{i} < L** or

**B**. Note that these

_{i}< B**L**and

**B**belong to one of the rectangles length and breadth(not necessarily the same rectangle).

Instead of fixing both

**L**and

**B**, we fix

**L**and then let’s try to find the maximum

**B**possible. So, we remove all rectangles with

**L**. Let’s say we have removed

_{i}< L**m**rectangles now. We can remove

**M - m**more rectangles now. As we want to maximize

**B**, we should remove rectangles with least

**B**of the remaining rectangles.

_{i}How do we implement this with good complexity? Doing it naively would result in high complexity.

Look at this psuedo code for the algorithm:

```
//reduces the count of key x in mymap
//remove the key if count is reduced to 0
map_dec(mymap, x):
mymap[x]--;
if mymap[x]==0:
myamp.erase(x)
map < int , int > mymap;
//we keep a list of pair A
//we mark all breadths in a map
for i=0 to N-1:
A[i].first, A[i].second = input
mymap[A[i].second]++
sort(A)
//we unmark the first M breadths after sorting
for i=0 to M-1:
map_dec(mymap, A[i].second)
ans=0
for i=m-1 to -1:
//i denotes that we have deleted first (i+1) elements of sorted A
//A[i+1].first is the smallest length now
//of all the marked breadths we take the minimum breadth
curans = A[i+1].first * mymap.begin()->first;
ans = max(ans, curans)
//we are done
if(i==-1)break;
//we mark the breadth of i'th rectangle
//because in next iteration we'll consider it to be present
S.insert(A[i].second);
//now, in next iteration we'll have an option to delete 1 more extra breadth
//so we delete the minimum breadth available to us till now
map_dec(mymap, mymap.begin()->first);
print ans
```

Complexity: **O(N log N + M log N)**.