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 all subtasks:
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.
Subtask 1 [10%]
query
will be called at most times.
Subtask 2 [20%]
query
will be called at most times.
Subtask 3 [30%]
query
will be called at most times.
Subtask 4 [40%]
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 
Comments
Pro tip: Do not use vectors like me. Huge timewasters 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.
DO NOT have debug output in your
init()
function or you will get WAMy 2D sparse table TLEs on the last subtask. How can I optimise my code?
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.
Thanks, that worked!
I got
RTE (failed initializing)
when submitting my code but after resubmitting the same code it got ACSounds like undefined behaviour :(