Fişierul intrare/ieşire:nrsubsecv.in, nrsubsecv.outSursăInfoarena Cup 2012
AutorAndrei ParvuAdăugată deCezarMocanCezar Mocan CezarMocan
Timp execuţie pe test0.9 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Nrsubsecv

Sandu Marele Cugetător este cunoscut pentru faptul că tot timpul îşi pune foarte multe întrebări filosofice. Astăzi, având un şir de N elemente, el doreşte să răspundă la M întrebări de forma: Fiind date un x si y, câte subsecvenţe din şirul dat au elementul minim cuprins între x si y?.
Voi trebuie să îi arătaţi lui SMC că sunteţi la fel de preocupaţi de treburi filosofice ca şi el, şi să îi răspundeţi la cele M întrebări.

Date de intrare

Fişierul de intrare nrsubsecv.in conţine pe prima linie două numere naturale N si M, reprezentând numărul de elemente din şir, respectiv numărul de întrebări ale lui SMC. A doua linie conţine N numere naturale, reprezentând elementele şirului. Următoarele M linii conţin fiecare câte două numere naturale x si y, x ≤ y, cu semnificaţia din enunţ.

Date de ieşire

Fişierul de ieşire nrsubsecv.out trebuie să conţină M linii, pe a i-a linie aflându-se răspunsul la a i-a întrebare din fişierul de intrare.

Restricţii

  • 1 ≤ N ≤ 1.000.000
  • 1 ≤ M ≤ 100.000
  • Elementele şirului se află în intervalul [0, 106]
  • 0 ≤ x ≤ y ≤ 106
  • Atenţie! SMC recomandă tipuri de date pe 64 de biţi cu semn pentru afişarea răspunsului.

Exemplu

nrsubsecv.innrsubsecv.out
12 3
2 4 3 2 5 2 3 5 7 1 3 2
2 2
3 3
5 5
37
6
3

Explicaţie

Cele 37 de subsecvente care au minimul 2 sunt: [1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [1, 9], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [2, 9], [3, 4], [3, 5], [3, 6], [3, 7], [3, 8], [3, 9], [4, 4], [4, 5], [4, 6], [4, 7], [4, 8], [4, 9], [5, 6], [5, 7], [5, 8], [5, 9], [6, 6], [6, 7], [6, 8], [6, 9], [11, 12] şi [12, 12].

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content