## 2-Dimensional Range Minimum Query

View as PDF

Points: 17 (partial)
Time limit: 2.0s
Memory limit: 1G

Author:
Problem type
Allowed languages
C++

You are given a -dimensional array of integers of size . We will call this array . You are then required to answer multiple queries for the minimum integer in a given submatrix.

Formally, given integers , determine .

#### Implementation Details

You should implement the following functions:

void init(std::vector<std::vector<int>> arr);

• : a -dimensional array of size .
int query(int a, int b, int c, int d);

• : the lower bound on the first dimension of the submatrix.
• : the upper bound on the first dimension of the submatrix.
• : the lower bound on the second dimension of the submatrix.
• : the upper bound on the second dimension of the submatrix.
• This function should return the minimum integer in the submatrix formed by .

It is guaranteed that init will be called exactly once, and that this call will be made before any calls to query.

#### Constraints

for
for all calls to query
for all calls to query

Disclaimer: were generated randomly.
Your answer will be considered correct if the bitwise of the answers to all the queries matches the expected result.

query will be called at most times.

query will be called at most times.

query will be called at most times.

query will be called at most times.

#### Sample Interaction

Please note that the sample will not appear in any of the test cases.

Function Call Return Value
init({{1, 2}, {3, 4}})
query(0, 1, 0, 1) 1
query(1, 1, 0, 1) 3
query(0, 0, 1, 1) 2

• commented on Oct. 15, 2021, 12:01 p.m. edited

Pro tip: Do not use vectors like me. Huge time-wasters were initializing the vector or the operator overloading to index them where a raw stack array would be much faster. Took a long time to figure that one out.

• commented on March 22, 2020, 4:36 a.m.

DO NOT have debug output in your init() function or you will get WA

• commented on Jan. 21, 2020, 2:33 a.m.

My 2D sparse table TLEs on the last subtask. How can I optimise my code?

• commented on Jan. 21, 2020, 3:00 a.m.

Swapping the dimensions of the sparse table (ie. putting the smaller dimensions first) fixed my code when I got TLE on the last batch. It seems that this also allows your solution to pass.

• commented on Jan. 21, 2020, 3:04 a.m.

Thanks, that worked!

• commented on Jan. 3, 2020, 12:55 p.m.

I got RTE (failed initializing) when submitting my code but after resubmitting the same code it got AC

• commented on Jan. 3, 2020, 1:16 p.m.

Sounds like undefined behaviour :(