MATSUM - Matrix Summation
A N × N matrix is filled with numbers. BuggyD is analyzing the matrix, and he wants the sum of certain submatrices every now and then, so he wants a system where he can get his results from a query. Also, the matrix is dynamic, and the value of any cell can be changed with a command in such a system.
Assume that initially, all the cells of the matrix are filled with 0. Design such a system for BuggyD. Read the input format for further details.
The first line of the input contains an integer t, the number of test cases. t test cases follow.
The first line of each test case contains a single integer N (1 <= N <= 1024), denoting the size of the matrix.
A list of commands follows, which will be in one of the following three formats (quotes are for clarity):
- "SET x y num" - Set the value at cell (x, y) to num (0 <= x, y < N).
- "SUM x1 y1 x2 y2" - Find and print the sum of the values in the rectangle from (x1, y1) to (x2, y2), inclusive. You may assume that x1 <= x2 and y1 <= y2, and that the result will fit in a signed 32-bit integer.
- "END" - Indicates the end of the test case.
For each test case, output one line for the answer to each "SUM" command. Print a blank line after each test case.
Input: 1 4 SET 0 0 1 SUM 0 0 3 3 SET 2 2 12 SUM 2 2 2 2 SUM 2 2 3 3 SUM 0 0 2 2 END Output: 1 12 12 13
long long giving tle
It is very hard to get it AC using 2D segTrees (QuadTrees)
A blank line after after every test case. Seriously!
AC With long long wa with int o.O
@those who are getting WAs . put a newline after each test case or use only int not long long .if this does not work then check your code again probably mistake is there.
As Ihtisham, I am getting error(SIGSEGV) although code runs fine on ideone. Can you please provide an example with two test cases? (This would also clarify the blank line issue).
strange TLE with long long. changed to int and AC :). anyway nice question. learned 2D-BITLast edit: 2014-01-02 09:48:20
code quá nhanh ...:
NO blank line between the tests!! costs me some WAs
use fast i/o ..
what are the constraints for t?