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.
Input
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.
Output
For each test case, output one line for the answer to each "SUM" command. Print a blank line after each test case.
Example
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
hide comments
UJtriumphsâ„¢:
2015-01-23 11:30:04
Hard to get AC!! Nice intial 2-D BIT |
|
Mahesh Mishra:
2015-01-05 20:47:42
1. "Print a blank line after each test case".
|
|
Archit Jain:
2014-12-20 13:43:47
long long giving tle |
|
Divyank Duvedi:
2014-12-01 20:49:02
It is very hard to get it AC using 2D segTrees (QuadTrees) |
|
Anant Kumar:
2014-10-13 22:01:00
A blank line after after every test case. Seriously!
|
|
GURVINDER SINGH:
2014-06-05 13:46:26
AC With long long wa with int o.O |
|
zicowa:
2014-04-20 12:26:08
@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. |
|
Olli Forty:
2014-01-17 16:32:23
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). |
|
Savan Popat:
2014-01-02 09:47:52
strange TLE with long long. changed to int and AC :). anyway nice question. learned 2D-BIT Last edit: 2014-01-02 09:48:20 |
|
code quá nhanh ...:
2013-12-18 15:29:33
NO blank line between the tests!! costs me some WAs |
Added by: | Matthew Reeder |
Date: | 2006-10-29 |
Time limit: | 1.029s |
Source limit: | 30000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Al-Khawarizm 2006 |