Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard
You’ve recently started an ice-cream business in a local school. During a day you have many suppliers delivering the ice-cream for you, and many students buying it from you. You are not allowed to set the prices, as you are told the price for each piece of ice-cream by the suppliers.
The day is described with a sequence of queries. Each query can be either
ARRIVE n c
, meaning that a supplier has delivered _n_pieces of ice-cream priced _c_each to you, or
BUY n t
, meaning that a student wants to buy n_pieces of ice-cream, having a total of _t_money. The latter is processed as follows: in case _n_cheapest pieces of ice-cream you have cost no more than _t(together), you sell those _n_cheapest pieces to the student; in case they cost more, she gets nothing. You start the day with no ice-cream.
For each student, output
HAPPY
if she gets her ice-cream, and
UNHAPPY
if she doesn’t.
Input
The input file contains between 1 and 105 queries (inclusive), each on a separate line. The queries are formatted as described above, either
ARRIVE n c
BUY n t
, 1 ≤ n, c≤ 106 , 1 ≤ t≤ 1012 .
Output
For each
BUY
-query output one line, containing either the word
HAPPY
or the word
UNHAPPY
(answers should be in the same order as the corresponding queries).
Example(s)
sample input
sample output
ARRIVE 1 1
ARRIVE 10 200
BUY 5 900
BUY 5 900
BUY 5 1000
HAPPY
UNHAPPY
HAPPY
基础线段树。
线段树维护每个点有的个数和总和。
需要给某个点加上一个个数,清空一个区间的值,查询一个区间的总价值和。
需要离线下,离散化处理、
Original: https://www.cnblogs.com/kuangbin/p/3703956.html
Author: kuangbin
Title: SGU 311. Ice-cream Tycoon(线段树)
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/546651/
转载文章受原作者版权保护。转载请注明原作者出处!