RMQSQ - Range Minimum Query
You are given a list of N numbers and Q queries. Each query is specified by two numbers i and j; the answer to each query is the minimum number between the range [i, j] (inclusive).
Note: the query ranges are specified using 0-based indexing.
Input
The first line contains N, the number of integers in our list (N <= 100,000). The next line holds N numbers that are guaranteed to fit inside an integer. Following the list is a number Q (Q <= 10,000). The next Q lines each contain two numbers i and j which specify a query you must answer (0 <= i, j <= N-1).
Output
For each query, output the answer to that query on its own line in the order the queries were made.
Example
Input: 3
1 4 1
2
1 1
1 2 Output: 4
1
hide comments
|
th3rd_br0:
2020-12-20 13:35:06
This is the problem where sparse table shines! (0.06s)
|
|
nagpur:
2020-12-06 01:15:14
@nikhil_33 the range is already in 0 index format, u must be decrementing , also increment l and r for 0 index and later decrement. |
|
ritikagarwal47:
2020-11-22 12:54:38
simple using sqrt decomposition! |
|
neerav_1:
2020-11-17 15:08:33
i am getting tle using seg tree..
|
|
nikhil_33:
2020-10-07 21:39:57
I am using sparse table and getting wrong answer after 5th case. Can anyone help me? Last edit: 2020-10-07 21:47:27 |
|
shahil198:
2020-09-12 09:01:52
using mo's algo its become very easy .. |
|
fuadul_hasan:
2020-09-12 03:37:46
pure segment tree ... very nice problem. |
|
paliya_64:
2020-09-01 15:10:46
not sure why but ,it even accepted my naive's solution, which I guessed to show TLE, xp |
|
insayn:
2020-08-28 20:55:55
AC with sqrt decomposition! |
|
sksinghl498:
2020-08-06 06:52:38
Bro it's so simple use sparse table .....than u can got the answer |
| Added by: | Joshua Kirstein |
| Date: | 2014-10-18 |
| Time limit: | 3s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
RSS