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
|
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 |
|
deerawat:
2020-07-30 12:26:14
First question with segment trees!! |
|
syed_tanveer:
2020-07-27 18:47:48
AC 0.04s , segment tree. |
|
i_spidey:
2020-07-23 20:45:15
Done at the first time using segment tree
|
|
scolar_fuad:
2020-06-06 20:04:27
solve first if you have learnt RMQ algorithm |
|
flashadarsh:
2020-05-23 12:48:18
Easy using sqrt decomposition :) |
|
raghav_sharma:
2020-05-15 17:05:49
i am using sparse table in python but it is giving tle. Can someone please tell why? |
|
angshuman_03:
2020-04-23 17:50:58
AC using sparse table!
|
|
medhruv7:
2020-04-03 00:05:03
AC one go , sparse table |
| Added by: | Joshua Kirstein |
| Date: | 2014-10-18 |
| Time limit: | 3s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
RSS