All submissions for this problem are available.
Aritra is working in Chemistry lab. There are N atoms initially each having a weight w. He observes the following activity occurring : In each step of reaction an atom(or a group of atoms) combines with another atom(or a group of atoms). Thus groups of atoms keep on forming with their weights increasing. Anxious Aritra wants to derive following results about the reaction.
1. After every combining step, Aritra wants to know the minimum weight among all the groups of atoms present after that step.
2. Aritra defines size (S) of a group of atoms as the number of atoms in that group and weight (W) of the group as the sum of weights of all atoms in that group. He considers one group superior over another if and only if it has either its size or weight strictly greater than that of the other group and the other quantity greater than or equal to that of other group. Aritra wants to find for each group of atoms, the number of groups it is superior to.
Note that If group x is not superior over group y then it doesn't imply that group y is superior over group x.
The first line of input contains two integers N and Q describing the number of atoms and the number of combination steps. Then N integers follow in next line describing the weights of N atoms. Then Q lines follow each containing two integers A and B denoting the indices(1 based) of atoms combining in that step.
You have to print Q+1 lines. First Q lines containing the minimum weight of all groups present after each combining step. Find for each group the number of groups it is superior to and print the values in ascending order in the last line
Note that the output of Q+1 line is independent of how you number the final group of atoms formed.
Subtasks and Constraints
Subtask 1:(20 points)
Subtask 2:(80 points)
Input: 5 2 4 6 4 6 5 1 2 4 5 Output: 4 4 0 1 2
It is quite clear that after both 1st and 2nd combination steps, the minimum weight present is 4 (of 3rd atom). Finally, there are 3 atom groups of size 1,2,2 and weights 4,10,11 respectively. Hence the first group is superior to 0, the second group to 1 and the last group to 2 groups.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, PYTH, PYTH 3.5|
Fetching successful submissions
If you are still having problems, see a sample solution here.