2-Dimensional Range Minimum Query

View as PDF

Submit solution


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

Author:
Problem type
Allowed languages
C++

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

Formally, given 4 integers a, b, c, d, determine \min{\{ arr[i][j] \mid a \le i \le b, c \le j \le d \}}.

Implementation Details

You should implement the following functions:

void init(std::vector<std::vector<int>> arr);
  • arr: a 2-dimensional array of size N \times N.
int query(int a, int b, int c, int d);
  • a: the lower bound on the first dimension of the submatrix.
  • b: the upper bound on the first dimension of the submatrix.
  • c: the lower bound on the second dimension of the submatrix.
  • d: the upper bound on the second dimension of the submatrix.
  • This function should return the minimum integer in the submatrix formed by a, b, c, d.

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:

1 \le N \le 1000
1 \le arr[i][j] \le 10^9 for 0 \le i, j \le N - 1
0 \le a \le b \le N - 1 for all calls to query
0 \le c \le d \le N - 1 for all calls to query

Disclaimer: arr[i][j], a, b, c, d were generated randomly.
Your answer will be considered correct if the bitwise xor of the answers to all the queries matches the expected result.

Subtask 1 [10%]

query will be called at most 1\,000 times.

Subtask 2 [20%]

query will be called at most 100\,000 times.

Subtask 3 [30%]

query will be called at most 1\,000\,000 times.

Subtask 4 [40%]

query will be called at most 10\,000\,000 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


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

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


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

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


    • 7
      Tzak  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.


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

        Thanks, that worked!


  • -4
    wleung_bvg  commented on Jan. 4, 2020, 7:36 p.m.

    The grader has been fixed. All submissions have been rejudged. Your verdict may change if your submission has undefined behaviour or is close to the time limit.


  • 7
    Plasmatic  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


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

      Sounds like undefined behaviour :(