P1937 [USACO10MAR] Barn Allocation G

Farmer John has recently opened a new barn and is now accepting stall-allocation requests from cows, since some stalls have better views. The barn contains $N$ stalls ($1 \le N \le 100{,}000$), labeled $1$ to $N$ for convenience. Stall $i$ can hold $C_i$ cows ($1 \le C_i \le 100{,}000$). The $i$-th cow wants to stroll in a contiguous range of stalls from $A_i$ to $B_i$ ($1 \le A_i \le B_i \le N$). In other words, this cow wants access to every stall in the interval $[A_i, B_i]$, and to satisfy this request you must reserve one unit of capacity in every stall of that interval for this cow. Given $M$ stall-allocation requests ($1 \le M \le 100{,}000$), determine the maximum number of cows whose requests can be satisfied (without building additional stalls).

- The first line contains two space-separated integers: $N, M$. - Lines $2$ to $N+1$: line $i+1$ contains a single integer $C_i$. - Lines $N+2$ to $N+M+1$: line $i+N+1$ contains two integers $A_i, B_i$.

Output a single line with the maximum number of requests that can be satisfied.

Consider the following example: ```plain 畜栏号: 1 2 3 4 5 +---+---+---+---+---+ 容纳空间: | 1 | 3 | 2 | 1 | 3 | +---+---+---+---+---+ Cow 1 XXXXXXXXXXX (1, 3) Cow 2 XXXXXXXXXXXXXXX (2, 5) Cow 3 XXXXXXX (2, 3) Cow 4 XXXXXXX (4, 5) ``` John clearly cannot satisfy all requests, since stalls $3$ and $4$ are over-requested. After testing, we find that we can satisfy cows $1, 3, 4$, so the answer for this testdata is $3$. Source: USACO 2010 March Gold Translator: @chrome01 Translated by ChatGPT 5