MALD Contest 1 P4 - Scratch Cat and Demolition

Points: 15 (partial)

Time limit: 1.0s

Java 2.0s

Python 3.0s

Memory limit: 512M

Author:

dawangk

Problem type

Okay, look, we can't do infinite destruction, or else I'm broke

To support the great cult of Mr. Scratch, the founder of ScratchLand, the Scratch Cats decided to demolish the healthcare district of Yuboland to make room for a Great Statue of Mr. Scratch. The healthcare district can be pictured as a number line with $N$ $N$ buildings, and the $i^\text{th}$ $i^{th}$ building has $h_i$ $h_{i}$ floors. However, for research purposes, $F$ $F$ floors in the district contain "Yubonic Plague" specimens.

The Scratch Cat decides to hire Scratch Cat construction workers for his demolition team. They will choose a segment $[L, R]$ $[L, R]$ $(1 \le L \le R \le N)$ $(1 \leq L \leq R \leq N)$ , the range of demolition. During one round, explosives will be laid, and all $h_i$ $h_{i}$ $(L \le i \le R)$ $(L \leq i \leq R)$ will be subtracted by $1$ $1$ . Since the Scratch Cat wants maximum damage, this process will continue as long as no top floors in the range $[L, R]$ $[L, R]$ contain Yubonic Plague specimens. The Scratch Cat is smart enough to know that destroying these floors could result in another pandemic.

Negative heights can potentially be created in demolition rounds. These are the basement floors and count towards destroyed floors. Yuboland buildings have so many basement floors that you can assume there is an "infinite" amount of them.

The Scratch Cat ~~forced~~ hired you to help determine the demolition interval for maximal destruction. Each interval must contain at least $1$ $1$ building with the virus, or his demolition team will never stop. The Scratch Cat certainly doesn't want to pay for that many explosives.

Constraints

$1 \le b_i \le N \le 10^6$ $1 \leq b_{i} \leq N \leq 10^{6}$

$1 \le F \le 3 \times 10^6$ $1 \leq F \leq 3 \times 10^{6}$

$1 \le h_i \le 2 \times 10^5$ $1 \leq h_{i} \leq 2 \times 10^{5}$

$1 \le f_i \le h_{b_i}$ $1 \leq f_{i} \leq h_{b_{i}}$

Subtask 1 [10%]

$1 \le N \le 5 \times 10^3$ $1 \leq N \leq 5 \times 10^{3}$

Subtask 2 [20%]

All buildings will contain at least $1$ $1$ floor containing a specimen.

Subtask 3 [70%]

No additional constraints.

Input Specification

The first line will contain two space-separated integers $N$ $N$ and $F$ $F$ , the number of buildings and floors.

The next line will contain $N$ $N$ space-separated integers, the $i^\text{th}$ $i^{th}$ integer will be $h_i$ $h_{i}$ .

The following $F$ $F$ lines will contain two space-separated integers $b_i$ $b_{i}$ and $f_i$ $f_{i}$ , the building and floor number of the $i^\text{th}$ $i^{th}$ forbidden floor.

Output Specification

Output the maximum of floors that can be destroyed. Building and basement floors all count towards floors destroyed.

Sample Input

Copy

6 4
1 2 3 4 5 6
6 5
5 1
4 1
6 3

Sample Output

Copy

Explanation

The optimal way to destroy the buildings is to choose $[1, 5]$ $[1, 5]$ as the interval. Scratch Cat construction workers will keep blowing up this range until the forbidden floor in building $4$ $4$ is exposed after $3$ $3$ rounds. This will cause $3 \times 5$ $3 \times 5$ or $15$ $15$ floors to be destroyed. Note that $[1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]$ $[1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]$ are all invalid ranges because the Scratch Cat's demolition team will never stop blowing up these ranges.

The diagram above shows the floors destroyed by each round of explosives.

After the unauthorized destruction of $15$ $15$ floors with illegal explosives, the Scratch Cat was quickly arrested. Despite the arrest of the Scratch Cat, this problem is still in the contest, and you (hopefully) decide to continue working on the problem.

Comments

There are no comments at the moment.