问题 BF: Emergency Handling
内存限制：128 MB
时间限制：11.000 S
评测方式：文本比较
命题人：
提交：96
解决：39
题目描述
Indonesia, as well as some neighboring Southeast Asian countries and some other East Asian countries, is located in the Pacific Ring of Fire which rather frequently causes volcanic eruptions, large earthquakes, and tsunamis. Handling hospital emergency situations effectively is critical for such countries laden with natural disasters. A leading local hospital recently has asked some computer scientists to help them optimize their emergency handling especially under large volume of cases. During a day, patients may come to the emergency department with different severity (e.g. suffering from broken bone is more severe than suffering from flu) and with different rate of increase of severity (e.g., burn injury if not treated immediately can be very dangerous, compared to broken bone) For a simplified model, suppose a patient arrives at time t0 with initial severity s(t0) and rate of increase of severity per unit of time r. Then the severity at time t becomes s(t) = s(t0) + r·(t−t0) The hospital has only limited facility and workforce to handle the patients so they want to prioritize the handling the best they can. More precisely, at any time t, if the hospital can admit one of the patients to treat, it must choose the patient with the highest severity s(t) at that time t. If there are ties, it must choose the patient with the highest rate of increase of severity r. If there are still ties, any one of the tied patients can be chosen. We assume that once a patient is chosen and given care, the patient will be safe and is no longer in the list of waiting patients. Given the sequence of incoming patients and admission of patients, help the hospital to determine the best patient to admit at each admission event.
输入
The first line of input contains an integer T (T ≤ 5) denoting the number of cases. Each case begins with an integer N (1 ≤ N ≤ 100,000) denoting the number of events. For the next N lines, each line describes either an incoming patient or an admission event. • For an incoming patient, the line contains a character ‘P’ and three integers t0, s(t0) and r that describe the patient (0 ≤ t0 ≤ 106; 0 ≤ s(t0) ≤ 108; 0 ≤ r ≤ 100). • For an admission, the line contains a character ‘A’ followed by an integer t, which is the time of the event. You may assume that there is at least one patient waiting in the emergency department when this admission event occurs. The events are specified in strictly increasing order of time. The number of ‘P’ and ‘A’ events will be roughly balanced.
输出
For each case, output ‘Case #X:’ in a line, where X is the case number starts from 1. For each of the admission event, output two integers separated by a single space: the current severity of the chosen patient at the admission time and that patient’s rate of increase of severity.
样例输入 复制
2
9
P 10 10 1
P 30 20 1
A 35
P 40 20 2
P 60 50 3
A 75
P 80 80 3
A 100
A 110
6
P 1 10 2
A 5
P 10 10 1
P 11 1 10
A 15
A 20
样例输出 复制
Case #1:
35 1
95 3
140 3
160 2
Case #2:
18 2
41 10
20 1