수량 부분 체결 호가창

문제

중고 티켓 거래소의 호가창 서버를 구현하려 합니다. 판매자는 가격과 수량 을 함께 올리고, 체결 엔진은 한 번에 원하는 장 수 만큼 가격 순서대로 사갑니다. 이때 한 주문이 통째로 나가지 않고 일부만 체결 될 수 있습니다.

명령 문자열 배열 commands가 주어집니다. 각 명령은 다음 세 가지 중 하나입니다.

• 체결은 장 단위 로 이루어집니다. 맨 앞 주문의 잔량이 n보다 적으면 그 주문을 다 쓰고 다음 가격의 주문으로 넘어가 계속 채웁니다.
• 호가창에 남은 총 수량이 n보다 적으면 있는 만큼만 체결하고 끝냅니다. (호가창이 비어 있다면 그 DEAL 명령은 아무 일도 하지 않습니다.)
• 같은 가격의 주문이 여러 건일 수 있습니다. 이때 어느 건부터 체결하든 결과는 같습니다.

모든 명령을 순서대로 처리한 뒤, 호가창에 남은 주문을 보고 [최고가, 최고가의 잔량 합, 최저가, 최저가의 잔량 합]을 반환하는 solution(commands) 함수를 작성하세요. 잔량 합은 그 가격의 주문들이 여러 건이면 모두 더한 값 입니다. 남은 주문이 하나도 없으면 [-1, 0, -1, 0]을 반환합니다.

예시

예시 1 설명 500×3, 800×2, 300×4가 쌓인 상태에서 DEAL HIGH 4는 800짜리 2장을 모두 쓰고 모자란 2장을 500에서 채웁니다 (500은 1장 남음). 이어서 DEAL LOW 3은 300짜리 4장 중 3장을 체결합니다. 남은 주문은 500×1, 300×1이므로 [500, 1, 300, 1].

예시 2 설명 가격 120인 주문이 두 건(4장, 2장)이라 잔량 합은 6장입니다. 5장을 체결하면 1장이 남고, 최고가와 최저가가 모두 120이므로 [120, 1, 120, 1].

예시 3 설명 DEAL LOW 10은 남은 2장만 체결하고 끝납니다. 빈 호가창에 들어온 DEAL HIGH 1은 아무 일도 하지 않습니다. 그 뒤 등록된 70×3만 남습니다.

제약 조건

• 1 ≤ commands.length ≤ 100,000
• 1 ≤ p ≤ 1,000,000,000 (정수)
• 1 ≤ q ≤ 1,000,000 (정수)
• 1 ≤ n ≤ 3,000,000 (정수)
• 명령 문자열은 항상 위 세 형식 중 하나로 주어지며, 각 항목은 공백 하나로 구분됩니다.
• 매 DEAL마다 남은 주문 전체를 정렬하거나 순회하는 방식은 대형 입력에서 시간 초과가 발생하도록 테스트가 설계되어 있습니다.

시간 복잡도 목표: O(N log N)