A grid with r rows and c columns has one integer in each cell. The top row is row 1 and the leftmost column is column 1. q questions follow; each gives four numbers r₁ c₁ r₂ c₂ and asks for 'the sum of all numbers in the rectangle made of rows r₁ to r₂ and columns c₁ to c₂ (both ends included)'. Print each answer on its own line, in the order given.
The first line gives r, c and q, then r lines each give that row's c numbers, then q lines give the questions, all separated by spaces.
Input
1 ≤ r, c ≤ 100, 1 ≤ q ≤ 10,000, every cell is between -10⁶ and 10⁶, 1 ≤ r₁ ≤ r₂ ≤ r, 1 ≤ c₁ ≤ c₂ ≤ c
Output
q lines, the sum of the rectangle for each question
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Adding up the cells again for each question costs up to 10,000 questions × 10,000 cells = 100 million additions. Python cannot finish in time, and Craykon passes its execution-step limit (about 50 million) and stops. Build the 2D prefix sum P[i][j] = 'sum of the rectangle from (1,1) to (i,j)' once with P[i][j] = a[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1] (row 0 and column 0 are 0); then each answer is P[r₂][c₂] - P[r₁-1][c₂] - P[r₂][c₁-1] + P[r₁-1][c₁-1]. Three traps: subtracting with r₁, c₁ instead of r₁-1, c₁-1 drops the top row and left column. It is easy to forget to add back the top-left piece that was subtracted twice. And sums reach 10⁴ × 10⁶ = 10¹⁰, which overflows int (about 2.1 billion) in C, C++, Java and C# — use long/long long. Python integers are unbounded, and JavaScript, TypeScript and Craykon are exact up to 2^53, so they are fine. Making a 2D array differs by language: Python [[0] * (c + 1) for _ in range(r + 1)] ([[0] * (c + 1)] * (r + 1) is wrong: every row is the same list), JS Array.from({ length: r + 1 }, () => new Array(c + 1).fill(0)), Java new long[r + 1][c + 1] (zero-filled), C# rectangular array new long[r + 1, c + 1] with P[i, j], C a global long long P[101][101], C++ vector<vector<long long>>. Craykon stacks a NewList(c + 1, 0) per row with P.Add(…) — each row has 101 cells, far under the list limit of 10,000 items.
Pythonmain.py · 19 lines
import sysdata = sys.stdin.buffer.read().split()r, c, q = int(data[0]), int(data[1]), int(data[2])pos = 3# P[i][j] = 왼쪽 위 (1,1)부터 (i,j)까지 직사각형의 합. 0번째 줄·칸은 0으로 둔다P = [[0] * (c + 1) for _ in range(r + 1)]for i in range(1, r + 1): for j in range(1, c + 1): P[i][j] = int(data[pos]) + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] pos += 1out = []for _ in range(q): r1, c1, r2, c2 = map(int, data[pos:pos + 4]) pos += 4 out.append(P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1])print("\n".join(map(str, out)))
JavaScriptmain.js · 19 lines
const t = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [r, c, q] = t;let pos = 3;// P[i][j] = 왼쪽 위 (1,1)부터 (i,j)까지 직사각형의 합. 0번째 줄·칸은 0으로 둔다const P = Array.from({ length: r + 1 }, () => new Array(c + 1).fill(0));for (let i = 1; i <= r; i++) { for (let j = 1; j <= c; j++) { P[i][j] = t[pos++] + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1]; }}const out = [];for (let k = 0; k < q; k++) { const [r1, c1, r2, c2] = t.slice(pos, pos + 4); pos += 4; out.push(P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1]);}console.log(out.join("\n"));