<ПРЕД Задача:
СЛЕД>
Задачу решили 427 пользователей: ...
UserDateAttemptTimeCMSC
alt_ua16 feb 2008C++904.9252 
alt_ua16 feb 2008C++1004.6060 
abortmozga.ru26 sep 2010C++4002.99168 
lychees01 jul 2011C++4202.00174 
hbmhalley26 jul 2010C++302.10184 
fetetriste23 nov 2007C++1002.13186 
abortmozga.ru25 sep 2010C++2502.78186 
abortmozga.ru25 sep 2010C++1802.01190 
QWE15 nov 2007Kylix604.48196 
WsemirZ27 dec 2007Kylix902.85202 
QWE25 sep 2007Kylix304.19205 
abortmozga.ru25 sep 2010C++1702.00206 
QWE25 sep 2007Kylix204.00207 
Vladislav27 jun 2012Kylix603.14208 
Philip_PV12 jul 2008C602.47210 
tnndye12 may 2007C++502.56213 
Языки
C++
341
Kylix
62
C
33
Java
10
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Задача RMQ

Time limit = 5 секунд(ы)

Memory limit = 32000 Kb

Вам дан большой массив вещественных чисел:

a[0], a[1], ... a[N-1]

Задачу RMQ (Range Minimal Query) можно сформулировать так:

RMQ(i,j) = "найти минимум из чисел a[i], a[i+1], ..., a[j-1]".

Ваша программа должна решать заданный набор задач RMQ.

Вход. Входные данные имеют следующий формат:

N
a[0] a[1] ...   a[N-1]
M
i1 j1
i2 j2
...

iM jM

Here N ≤ 250000, M ≤ 500000, 0 ≤ ik < N, 0 < jkN, ik < jk.

Выход. Ваша программа должна вывести M чисел b1, b2, ..., bM, разделённых пробелами, где

bk = MIN (a[ik], a[ik + 1], ..., a[jk — 1]).

Вход#1
10
1 2 3 4 5 6 7 8 9 10
16
0 1
0 2
0 3
0 4
3 4
3 5
3 6
3 7
3 8
3 9
3 10
0 10
9 10
8 10
7 10
5 6
Выход#1
1.000000
1.000000
1.000000
1.000000
4.000000
4.000000
4.000000
4.000000
4.000000
4.000000
4.000000
1.000000
10.000000
9.000000
8.000000
6.000000

Вход#2
10
3.86934 7.28362 2.15556 14.75963 0.33240 17.12550 -0.71121 13.90834 -1.13470 5.99831
11
6 10
0 1
5 10
1 9
0 6
0 10
2 5
3 10
5 9
0 8
2 10
Выход#2
-1.134700
3.869340
-1.134700
-1.134700
0.332400
-1.134700
0.332400
-1.134700
-1.134700
-0.711210
-1.134700



Автор:
Классическая задача. Тесты и описание - Артём Ворожцов.
11 мая 2006

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 18.207.106.142