Fișierul intrare/ieșire: bitone.in, bitone.out Sursă Cerc informatică Vianu
Autor Cristian Frâncu Adăugată de francuCristian Francu francu
Timp execuție pe test 1.6 sec Limită de memorie 8500 KB
Scorul tău N/A Dificultate normalnormalnormalnormalnormal

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.

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

Indicii de rezolvare

Arată 2 categorii