SHARE
TWEET

Untitled

a guest Apr 26th, 2019 88 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.     Complexitate O(n log n + T log n)
  3. */
  4. #include <bits/stdc++.h>
  5. #define nmax 200003
  6. using namespace std;
  7.  
  8. int a[nmax], n;
  9.  
  10. /// cauta binar cea mai din stanga pozitie p
  11. /// cu proprietatea ca x <= a[p]
  12. int CautBin1(int x)
  13. {
  14.     if (a[n] < x) return n + 1;
  15.     if (x <= a[1]) return 1;
  16.     int st, dr, m, p;
  17.     st = 1; dr = n; p = 1;
  18.     while (st <= dr)
  19.     {
  20.         m = (st + dr) / 2;
  21.         if (x <= a[m])
  22.         {
  23.             p = m; dr = m - 1;
  24.         }
  25.         else st = m + 1;
  26.     }
  27.     return p;
  28. }
  29.  
  30. /// cauta binar cea mai din dreapta pozitie p
  31. /// cu proprietatea ca a[p] <= y
  32. int CautBin2(int y)
  33. {
  34.     if (a[n] <= y) return n;
  35.     if (a[1] > y) return 0;
  36.     int st, dr, m, p;
  37.     st = 1; dr = n; p = 1;
  38.     while (st <= dr)
  39.     {
  40.         m = (st + dr) / 2;
  41.         if (a[m] <= y)
  42.         {
  43.             p = m; st = m + 1;
  44.         }
  45.         else dr = m - 1;
  46.     }
  47.     return p;
  48. }
  49.  
  50. int main()
  51. {
  52.     int i, p, q, T, x, y;
  53.     cin >> n >> T;
  54.     for (i = 1; i <= n; i++)
  55.         cin >> a[i];
  56.  
  57.     sort(a + 1, a + n + 1);
  58.  
  59.     while (T--)
  60.     {
  61.         cin >> x >> y;
  62.         p = CautBin1(x);
  63.         q = CautBin2(y);
  64.         cout << (q - p + 1) << "\n";
  65.     }
  66.  
  67.     return 0;
  68. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top