문제 번호 5068 --Seating

5068: Seating

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 3  해결 문제 수: 0
[제출][채점상황][게시판][:]

문제 설명

To earn some extra money, the cows have opened a restaurant in their barn specializing in milkshakes. The restaurant has N seats (1 <= N <= 500,000) in a row. Initially, they are all empty. Throughout the day, there are M different events that happen in sequence at the restaurant (1 <= M <= 300,000). The two types of events that can happen are: 1. A party of size p arrives (1 <= p <= N). Bessie wants to seat the party in a contiguous block of p empty seats. If this is possible, she does so in the lowest position possible in the list of seats. If it is impossible, the party is turned away. 2. A range [a,b] is given (1 <= a <= b <= 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..M+1: Each line describes a single event. It is either a line of the form "A p" (meaning a party of size p arrives) or "L a b" (meaning that all cows in the range [a, b] leave).

출력

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

입력예시

10 4
A 6
L 2 4
A 5
A 2

출력예시

1

도움말

Party #3 is turned away. All other parties are seated.


출처

[제출][채점상황]