Advertisement
ke_timofeeva7

бинпоиск для кирюши

Mar 22nd, 2021
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.03 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. #include <string>
  4. #include <sstream>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <memory.h>
  8. #include <stdio.h>
  9. #include <vector>
  10. #include <stack>
  11. #include <deque>
  12. #include <queue>
  13. #include <vector>
  14. #include <set>
  15. using namespace std;
  16.  
  17. vector <int> vc;
  18.  
  19. int left_bin(int l, int r, int key)
  20. {
  21.     int m;
  22.     while (r - l > 1)
  23.     {
  24.         m = (r + l) / 2;
  25.         if (vc[m] > key)
  26.         {
  27.             r = m;
  28.         }
  29.         else
  30.         {
  31.             l = m;
  32.         }
  33.     }
  34.     /*if (vc[l] > key && l + 1 < vc.size())
  35.     {
  36.         return  l + 1;
  37.     }*/
  38.     if (vc[vc.size() - 1] < key || vc[r] == key)
  39.     {
  40.         return r;
  41.     }
  42.     if (vc[l] <= key)
  43.     {
  44.         return l;
  45.     }
  46.      
  47.     return -1;
  48. }
  49.  
  50. int right_bin(int l, int r, int key)
  51. {
  52.     int m;
  53.     while (r - l > 1)
  54.     {
  55.         m = (r + l) / 2;
  56.         if (vc[m] >= key)
  57.         {
  58.             r = m;
  59.         }
  60.         else
  61.         {
  62.             l = m;
  63.         }
  64.     }
  65.     /*if (vc[r] > key && r + 1 < vc.size())
  66.     {
  67.         return  r + 1;
  68.     }*/
  69.     if (vc[0] > key || vc[l] == key)
  70.     {
  71.         return l;
  72.     }
  73.     if (vc[r] >= key)
  74.     {
  75.         return r;
  76.     }
  77.     return -1;
  78. }
  79.  
  80.  
  81. int main() {
  82.     int n, q;
  83.     cin >> n;
  84.  
  85.     for (int i = 0; i < n; i++)
  86.     {
  87.         cin >> q;
  88.         vc.push_back(q);
  89.     }
  90.  
  91.     sort(vc.begin(), vc.end());
  92.  
  93.     /*for (int i = 0; i < n; i++)
  94.     {
  95.         cout << vc[i] << " ";
  96.     }
  97.     cout << endl;*/
  98.  
  99.     int k, l, r, a1, a2;
  100.     cin >> k;
  101.  
  102.     for (int i = 0; i < k; i++)
  103.     {
  104.         cin >> l >> r;
  105.         a1 = left_bin(0, n - 1, r);
  106.         if (a1 == -1)
  107.         {
  108.             cout << 0 << " ";
  109.         }
  110.         else
  111.         {
  112.             a2 = right_bin(0, n - 1, l);
  113.             if (a2 == -1)
  114.             {
  115.                 cout << 0 << " ";
  116.             }
  117.             else
  118.             {
  119.                 cout << a1 - a2 + 1 << " ";
  120.             }
  121.         }
  122.     }
  123.     system("pause");
  124.     return 0;
  125.  
  126. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement