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.
