다이아몬드 V설명
여분의 돈을 벌기 위해, 소들은 헛간에 밀크셰이크 전문 식당을 열었다. 이 식당에는 N개의 좌석 (1 <= N <= 500,000)이 한 줄로 놓여 있다. 처음에는 모든 좌석이 비어 있다.
하루 동안 식당에서는 M개의 서로 다른 사건이 순서대로 일어난다 (1 <= M <= 300,000). 일어날 수 있는 사건의 종류는 다음 두 가지이다.
-
크기가 p인 일행이 도착한다 (1 <= p <= N). 베시(Bessie)는 이 일행을 연속한 p개의 빈 좌석에 앉히려고 한다. 가능하다면, 좌석 목록에서 가능한 가장 낮은 위치에 앉힌다. 불가능하다면, 일행은 돌려보내진다.
-
구간 [a,b]가 주어지고 (1 <= a <= b <= N), 그 구간의 좌석에 앉아 있던 모든 손님이 떠난다.
하루 동안 돌려보내진 일행의 총 수를 세는 것을 도와주자.
제약
입력 형식
첫째 줄: 공백으로 구분된 두 정수 N과 M.
둘째 줄부터 M+1번째 줄까지: 각 줄은 하나의 사건을 설명한다. "A p" 형태의 줄(크기가 p인 일행이 도착)이거나 "L a b" 형태의 줄(구간 [a, b]에 있는 모든 소가 떠남)이다.
출력 형식
돌려보내진 일행의 수.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
seating.in · 출력을 쓸 파일 seating.out예제 1
입력
10 4
A 6
L 2 4
A 5
A 2출력
1설명
Output details: Party #3 is turned away. All other parties are seated.
문제 정보
태그
