| Submit | All submissions | Best solutions | Back to list |
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
| Added by: | Joshua Kirstein |
| Date: | 2014-10-18 |
| Time limit: | 3s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
hide comments
|
|||||||||||||
|
2016-09-22 12:35:32
too hard!!! Last edit: 2016-09-22 12:44:19 |
|||||||||||||
|
2016-09-17 08:44:08
Square root decomposition also works. |
|||||||||||||
|
2016-09-12 14:11:09
Segment tree faster than sparse table . Compare O(NlogN+Q) with O(N+QlogN). |
|||||||||||||
|
2016-07-02 23:14:45 gabbar
using array instead of a vector resulted in AC from TLE !! Last edit: 2016-07-05 08:46:34 |
|||||||||||||
|
2016-06-27 13:30:07 kartikay singh
Sparse Table ... :-) |
|||||||||||||
|
2016-06-17 21:37:41
Why not sparse tables? AC! |
|||||||||||||
|
2016-01-27 09:23:04
easy .accepted in one go. |
|||||||||||||
|
2016-01-25 20:38:05
Tried using MO algorithm . BUt gave tle . Think of segment tree So allowed complexity :O(Mlog(n)) and not allowed is >=(M*sqrt(n)). for beginners edit:: ISHPREET http://ideone.com/WvW0Bt .. here is the updated code And Got accepted with MO's algorithm . Illl take back my last message :D .... Good que for beginners Last edit: 2016-06-07 15:10:08 |
|||||||||||||
|
2015-12-22 21:20:39
I tried solving using both strategies and the result is that segment tree used 0.18 seconds/3.3MB while sparse table algorithm used 0.27 seconds/4.1MB So I guess that sparse table lost because initializing 2D vector cost a lot of time. To compensate this, the judge should ask more queries so we could see that sparse table would beat segment tree in overall time. Both algorithms are written in top-down approach (recursive function). If you ask me which is easier to implement, I would suggest segment tree because the intuition is strong in this one. Last edit: 2015-12-22 21:22:18 |
|||||||||||||
|
2015-12-22 19:23:41
This problem can be solved using segment tree or sparse table algorithm. In this case, sparse table is more efficient because the array is static and sparse algorithm runs faster. |
|||||||||||||
RSS