11783번 - HAPPINESS 다국어

Monetary system in X-land is a bit strange. There are banknotes with values of all integer numbers from 1 to M. There is another strange rule in the shops of X-land – the customer can never receive change, but also cannot leave a tip – in other words the customer must always pay the exact value of his purchases. If he does not have the exact sum for his purchase, then he cannot buy. Imagine what inconvenience this creates for the customers. 

Niya is a girl from X-land. Like all other persons, she constantly fights against the rules described above. She always knows her set of banknotes – let’s assume their values are a₁, a₂,…,a_N. All those values are between 1 and M and she may possess more than one banknote of a kind. Also the sequence of values a₁, a₂,…….,a_N, is not ordered in any way. Niya feels happy, when entering a shop, she may buy any combination of goods with total price equal to any number between 1 and the total sum of her banknotes a₁ + a₂ + ... + a_N. In that case, when she is shopping, she must only consider her total amount of money without making complicated calculations of whether she can buy (or not) with her banknotes. 

Remark: Let us sort a₁, a₂,…….,a_N in ascending order. Let us denote S_i = 1+a₁+ a₂+…….+a_i. Necessary and sufficient condition to be able to represent each number between 1 and a₁+ a₂+…….+a_N as a sum of elements from the multiset a₁, a₂,…….,a_N, is that the following inequality S_i ≥ a_i+1 held true for each i>1 and a₁ = 1. 

As expected, Niya’s set of banknotes is changing after each purchase and also after each wage she receives – that’s why her happiness is variable. You can help the girl with a program. Your program will receive as an input the initial set of Niya’s banknotes and all the events that happen – purchases and wages. The program should be able to determine if Niya is happy in the beginning and after each event.

We should note that Niya feels happy also when she doesn’t have any money – then she just skips shopping and goes jogging.

Task

Write functions init() and is_happy(), which will be compiled with jury’s grader. These functions should serve to determine Niya’s happiness at the beginning and after each event. The functions will receive as parameters the starting set of banknotes and the sets of banknotes that are removed from the set (on purchases) and added to the set (on receiving wage).

Implementation details

You should submit to the grading system a file happiness.cpp, which contains functions:

bool init(int coinsCount, long long maxCoinSize, long long coins[]).
bool is_happy(int event, int coinsCount, long long coins[]).

Parameters description:

• coinsCount – number of banknotes that are received (starting set or wage) or discarded (shopping).
• maxCoinSize – maximum value of one banknote. coins[] – array, in which in random order are given values of the banknotes (index starts from 0).
• event – event’s type :
  • −1 – Shopping;
  • 1 – Receiving wage.

The function init is called once by the grader at the beginning to set the starting set of Niya’s banknotes and then grader calls Q times function is_happy with event = −1 (shopping) or event = 1 (wage). After each call the called function should return true, if Niya feels happy with her current set of banknotes or false if she doesn’t.

File happiness.cpp should NOT contain function main(), but can contain other declarations and functions, necessary for correct working of functions init and is_happy. Your program should contain #include "happiness.h" in the beginning

Single positive integers N and M are given on the first row – initial count of Niya’s banknotes and maximum value of one banknote.

N positive integers are given on the second row, separated by spaces – values of banknotes in the initial set.

Non-negative integer Q is given on the third row – event’s count.

On each of the next Q rows one event is described – first, a value for the event is given: −1 (shopping) or 1 (receiving of a wage). After that a positive integer K is given – number of banknotes that are removed or added to Niya’s set. Last K integers are given, separated by intervals – values for the banknotes which are removed or added.

On the standard output the program will print Q+1 lines with 0 or 1 – "happiness" statuses of Niya at the beginning and after each event.

Let Nc denote the number of Niya’s banknotes at any given moment and K – the number of banknotes, used in any purchase or wage. Then we have:

• 0 ≤ Nc ≤ 200 000
• 0 ≤ Q ≤ 100 000
• 1 ≤ M ≤ 1012
• 1 ≤ K ≤ 5

It is guaranteed that in any call of is_happy with event = −1 (shopping) the set of banknotes given in coins[] is a subset of current Niya’s set of banknotes.