Instead of looking at the effect of these operations on the N numbers, look at the effect of these operations on: Number 1 Number 2 - Number 1 ... Number N - Number (N - 1)
On Sun, Aug 5, 2012 at 8:17 PM, ADEGEYE MAYOWA <[email protected]> wrote: > My algorithm O(t*m*n) > > > On Aug 5, 2012 6: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 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. > > -- 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.
