Question

Bună ziua! Ma poate ajuta cineva cu o rezolvare la problema #2276 de pe pbinfo, va rog?
Se consideră un șir a[1], a[2], …, a[n] de numere naturale. Se dau și T intervale închise de forma [x, y], cu x ≤ y.

Cerința
Pentru fiecare din cele T intervale de forma [x, y] trebuie să răspundeți la întrebarea: câte numere din șir aparțin intervalului [x, y]?

Date de intrare
Programul citește de la tastatură numerele n și T, apoi n numere naturale, separate prin spații, a[1], a[2], …, a[n]. Pe următoarele T linii se află câte două numere naturale x și y reprezentând un interval [x, y].

Date de ieșire
Programul va afișa pe ecran T linii. Pe fiecare linie i (i=1..T) se va afla un singur număr natural reprezentând răspunsul la a i-a întrebare.

Restricții și precizări
1 ≤ n, T ≤ 200 000
0 ≤ a[i] ≤ 2 000 000 000
0 ≤ x ≤ y ≤ 2 000 000 000



Exemplu
Intrare

9 7
6 1 3 5 3 3 9 20 9
4 10
0 100
0 1
500 506
3 3
10 18
3 9
Ieșire

4
9
1
0
3
0
7
​

Answer 1

Răspuns:

#include <iostream>

#include <algorithm>

using namespace std;

int q[200001], r[200001];

int main()

{

   int n, j, x, y, T, i, st, dr, s, d, m;

   cin >> n; cin >> T;

   for (i=1; i<=n; ++i) cin >> q[i];

   sort(q+1, q+n+1);

   for (j=1; j<=T; ++j)

   {

       cin >> x >> y;

       if (x>q[n] || y<q[1]) r[j]=0;

       else {

       st=1, dr=n;

        while (st<dr)

        {

           m = (st + dr) / 2;

           if (q[m] < x) st = m + 1;

           else  dr = m;

         }

         s=st;

       st=1, dr=n;

        while (st<dr)

        {

           m = (st + dr) / 2;

           if (q[m] <= y) st = m + 1;

           else  dr = m;

         }

         if ( q[st]>y) d=st-1;

         else d=st;

      r[j]=d-s+1;

       }

   }

   for (i=1; i<=T; ++i) cout << r[i]<<"\n";

   return 0;

}

Explicație: