ModularQuadrant
TCO19 SRM 744 · 2018-12-13 · by misof
Problem Statement
We are looking at the first quadrant of an infinite square grid. Its rows and columns are numbered starting from zero. Each cell (r,c) contains the number (max(r,c) mod 3).
Compute and return the sum of all cells (r,c) such that r1 <= r <= r2 and c1 <= c <= c2.
Constraints
- 0 <= r1 <= r2 <= 10^9.
- 0 <= c1 <= c2 <= 10^9.
0 2 1 4 Returns: 13
We want rows 0 through 2 and columns 1 through 4. The corresponding part of the grid looks as follows: 2201 1201 1201
2 2 0 7 Returns: 10
Now we are computing the sum of a single row that looks as follows: 22201201
4 8 0 5 Returns: 37
222222 111111 000000 222222 111112
12 34 56 78 Returns: 529
0 0 1000000000 1000000000 Returns: 1
Submissions are judged against all 141 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ModularQuadrant with a public method long long sum(int r1, int r2, int c1, int c2) · 141 test cases · 2 s / 256 MB per case