6085 : 힙 기반 이벤트 시뮬
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
힙 기반 이산 이벤트 시뮬레이션
우선순위 큐(이벤트 큐)를 시간 기준으로 정렬하여 이벤트를 처리합니다.
이벤트 형식:
- 타입 A: 값을 누적합(sum_A)에 더합니다.
- 타입 B: B 이벤트 카운트(cnt_B)를 증가시킵니다.
시뮬레이션 종료 조건: 이벤트 시간 > T (종료 시점)
최종 결과를
[제약 조건]
• 이벤트 수 $N$: $1 \le N \le 100{,}000$ (정수)
• 이벤트 발생 시간: $0 \le t \le 10^9$ (정수)
• 처리 우선순위: $1 \le p \le 10^9$ (정수)
우선순위 큐(이벤트 큐)를 시간 기준으로 정렬하여 이벤트를 처리합니다.
이벤트 형식:
시간 타입 값- 타입 A: 값을 누적합(sum_A)에 더합니다.
- 타입 B: B 이벤트 카운트(cnt_B)를 증가시킵니다.
시뮬레이션 종료 조건: 이벤트 시간 > T (종료 시점)
최종 결과를
A:합계 B:카운트 형식으로 출력합니다.[제약 조건]
• 이벤트 수 $N$: $1 \le N \le 100{,}000$ (정수)
• 이벤트 발생 시간: $0 \le t \le 10^9$ (정수)
• 처리 우선순위: $1 \le p \le 10^9$ (정수)
입력 설명
첫째 줄에 초기 이벤트 수 N (1 ≤ N ≤ 10,000)과 종료 시점 T가 주어집니다.
다음 N개의 줄에 이벤트 정보 (시간 타입 값)가 주어집니다.
다음 N개의 줄에 이벤트 정보 (시간 타입 값)가 주어집니다.
출력 설명
시뮬레이션 결과를 "A:누적합 B:카운트" 형식으로 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 10
1 A 5
2 B 0
3 A 3
4 B 0
5 A 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
A:10 B:2