Fișierul intrare/ieșire bitone.in, bitone.out Sursă Cerc informatică Vianu
Autor Cristian Frâncu Adăugată de avatar francu Cristian Francu francu
Timp de execuție pe test 1.6 sec Limită de memorie 8500 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii