Fișierul intrare/ieșire | bitone.in, bitone.out | Sursă | Cerc informatică Vianu |
---|---|---|---|
Autor | Cristian Frâncu | Adăugată de |
|
Timp de execuție pe test | 1.6 sec | Limită de memorie | 8500 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Bitone
O secvență de numere întregi se numește bitonă dacă este crescătoare la început, iar apoi descrescătoare. Mai precis, o secvență a1, a2, ..., an este bitonă dacă:
- este o secvență nedescrescătoare: a1 ≤ a2 ≤ ... ≤ an sau
- este o secvență necrescătoare: a1 ≥ a2 ≥ ... ≥ an sau
- exista un indice i pentru care a1 ≤ a2 ≤ ... ≤ ai ≥ ai+1 ≥ ... ≥ an
Cerință
Dată o secvență de numere întregi a1, a2, ..., an și niște întrebări de forma (i, j) să se răspundă pentru fiecare întrebare dacă subsecvența ai, ai+1, ..., aj este bitonă.
Date de intrare
Fișierul de intrare bitone.in conține pe prima linie numărul de numere din secvență, n. Pe a doua linie conține cele n numere ale secvenței, separate de spații. Pe a treia linie se află numărul de întrebări q. Pe următoarele q linii se vor găsi cîte două numere i j separate prin spațiu, reprezentînd întrebările la care se cere răspuns.
Date de ieșire
Fișierul de ieșire bitone.out va conține o singură linie cu q caractere 0 sau 1, fără spații între ele, caractere ce reprezintă răspunsurile la întrebări. Pentru fiecare întrebare veți răspunde 1 dacă subsecvența este bitonă, sau 0 în caz contrar.
Restricții
- 1 ≤ n ≤ 1.000.000
- -2.000.000.000 ≤ ai ≤ 2.000.000.000
- 1 ≤ q ≤ 1.000.000
- 1 ≤ i ≤ j ≤ n
Exemple
bitone.in | bitone.out | Explicație |
---|---|---|
10 10 19 19 18 18 21 21 11 11 13 6 9 10 6 10 4 8 8 10 1 7 3 3 |
101101 |
subsecvențele (6, 10) și (1, 7) nu sînt bitone. Toate celelalte sînt. |
15 10 11 13 13 6 8 8 8 4 4 5 9 0 2 2 10 2 10 9 13 1 3 7 14 4 7 1 9 3 10 4 11 13 13 9 9 |
0110000011 |
subsecvențele (9, 13) (1, 3) (13, 13) și (9, 9) sînt bitone. Toate celelalte nu. |