I guess this can be solved efficiently by using Segment_tree<http://en.wikipedia.org/wiki/Segment_tree> Thanks
PS This question is currently active on Codechef. Please refrain from providing the solution. -- Sajal On Sun, Aug 5, 2012 at 10:44 AM, 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.
