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
|
shanto09:
2020-03-11 14:50:53
AC with sparse table.. |
|
chaudhary_19:
2019-09-09 21:49:30
Sparse Table makes your life easier !!! |
|
chirayu_555:
2019-08-19 13:36:07
AC in one go. Easy with segment tree. |
|
necrofool:
2019-07-13 17:55:17
Easy using segment tree. Easier Using Sparse Table:) |
|
akash19jain:
2019-05-19 17:55:44
I tried many times using Segment tree but I am getting WA after the 5th case. Can anyone help me?
|
|
aj_254:
2019-04-26 10:33:42
ac in one go python 3.5 just increase recursion limit by sys.setrecursionlimit(15000) and use segment tree
|
|
riz1ahmed:
2019-04-26 01:03:05
AC With Square Root Decomposition. Now Try With Segment Tree. And then will try with Sparse TAble. |
|
amantu_amir:
2019-03-30 21:19:06
Easy one,
|
|
medhruv7:
2019-03-17 08:14:39
fake_death how u did in 0.01s can u send the code
|
|
|
medhruv7:
2019-03-17 08:12:57
0.03 sec for sparse tree with log optimization :) |
| Added by: | Joshua Kirstein |
| Date: | 2014-10-18 |
| Time limit: | 3s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
RSS