P3071 [USACO13JAN] Seating G

To earn some extra money, the cows have opened a restaurant in their barn specializing in milkshakes. The restaurant has $N$ seats in a row, numbered $1$ to $N$ ($1 \le N \le 500\,000$). Initially, all seats are empty. Throughout the day, there are $M$ events that happen in sequence ($1 \le M \le 300\,000$). Each event is one of the following: 1. A party of size $p$ arrives ($1 \le p \le N$). Bessie wants to seat the party in a contiguous block of $p$ empty seats. If this is possible, she seats them in the block whose starting position has the smallest index. If it is impossible, the party is turned away. 2. A range $[a, b]$ is given ($1 \le a \le b \le N$), and everybody in that range of seats leaves. Please help Bessie count the total number of parties that are turned away over the course of the day.

- Line 1: Two space-separated integers $N$ and $M$. - Lines $2$ to $M+1$: Each line describes a single event, either of the form "A p" (a party of size $p$ arrives) or "L a b" (all cows in the range $[a, b]$ leave).

- Line 1: The number of parties that are turned away.

There are 10 seats and 4 events. First, a party of 6 cows arrives. Then all cows in seats 2..4 depart. Next, a party of 5 arrives, followed by a party of 2. Party #3 is turned away. All other parties are seated. Translated by ChatGPT 5