If you keep track of the results as a set of nonoverlapping operations, that is, after adding 1 to papers 1 to 10 and subtracting 2 from pages 5 to 20, then you end up with three operations: +1 from 1-4, -1 from 5-10, and -2 from 11-20. Instead of applying each operation to potentially every number, you only have to apply it to this list of operations. The total number of operations you end up with is limited to 2M, since there are only 2M endpoints, and at the end you only have to compare 1 and the lower end of each interval to find the minimum, and N and the upper end of each interval to find the maximum. This should reduce it to O(t*m^2)
On Sun, Aug 5, 2012 at 1:44 PM, Vicky Sirwani <[email protected] > wrote: > Alice has *N* pieces of paper. These papers are numbered from *1* to *N*. > She writes down the numbers *1* to *N* in order (one number on each > paper), i.e. paper *i* has number *i* written on it. Bob messes the > numbers on these papers. He either *adds* a constant to a number or * > subtracts* a constant from the number. He performs *M* such operations. > Each operation is of the form: *w x y z* where each of them is an > integer. If *w = 1*, then Alice has to *add z* to every number on papers * > x* to *y* (*both inclusive*). If *w = 2,* then Alice has to *subtract z*from > every number on papers > *x* to *y* (*both inclusive*). After doing this, Bob challenges Alice to > tell him the range of this data, where *range* denotes the count of > numbers from the smallest number to the largest (See > here<http://www.wikihow.com/Find-the-Range-of-a-Data-Set>for more details). > Your task is to help Alice in finding the range. > Input: > > First line of input contains a single integer *T*, the number of test > cases. > Each test case starts with a line containing two space separated integers > *N* and *M*. > Then follow *M* lines. Each of these lines is of the form *w x y z*. Each > separated by a single space. > Output: > > For each test case output a single line containing the range of the new > data set after Bob's modifications. > Constraints: > > 1 ≤ T ≤ 20 > 1 ≤ M ≤ 10000 > 1 ≤ N ≤ 1000000 > 1 ≤ x ≤ y ≤ N > 0 ≤ z ≤ 100000 > > Example: > > *Input* > 1 > 10 2 > 2 3 6 4 > 1 5 9 1 > *Output:* > 11 > > > *Explanation:* Initially the papers are as follows: 1 2 3 4 5 6 7 8 9 10. > First operation decreases the numbers on paper number 3,4,5 and 6 by 4. > Now, the papers look like: 1 2 -1 0 1 2 7 8 9 10. The second operation > increases the numbers on papers 5 to 9 by 1. The numbers will now be 1 2 -1 > 0 2 3 8 9 10 10. Thus, the range is 10 - (-1) = 11. > > > > Can anyone help me with this??? > I can think of an O(t*m*n) solution, but it gives TLE. > Any efficient algorithm for this??? > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
