SHARE
TWEET

Untitled

a guest Apr 21st, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #define nmax 200002
  4. using namespace std;
  5. int n,t,v[nmax];
  6.  
  7. int cb_st(int x)
  8. {
  9.   int st = 1, dr = n, mijl;
  10.   while(st < dr)
  11.   {
  12.     mijl = (st + dr) / 2;
  13.     if(v[mijl] == x)
  14.       {
  15.        if(v[mijl - 1] == x)
  16.         {
  17.           int poz = mijl - 1;
  18.           while(v[poz] == x)
  19.             --poz;
  20.             return poz + 1;
  21.  
  22.         }
  23.           return mijl;
  24.       }
  25.     else
  26.       if(v[mijl] < x && v[mijl + 1] > x)
  27.         return mijl + 1;
  28.       else
  29.         if(v[mijl] < x)
  30.           st = mijl + 1;
  31.         else
  32.           dr = mijl;
  33.   }
  34.  return st;
  35. }
  36.  
  37. int cb_dr(int x)
  38. {
  39.   int st = 1, dr = n, mijl;
  40.   while(st < dr)
  41.   {
  42.     mijl = (st + dr) / 2;
  43.     if(v[mijl] == x)
  44.       {
  45.         if(v[mijl + 1] == x)
  46.           {
  47.             int poz = mijl + 1;
  48.             while(v[poz] == x)
  49.               ++poz;
  50.               return poz - 1;
  51.           }
  52.           return mijl;
  53.       }
  54.     else
  55.       if(v[mijl] < x && v[mijl + 1] > x)
  56.         return mijl;
  57.       else
  58.         if(v[mijl] < x)
  59.           st = mijl + 1;
  60.         else
  61.           dr = mijl;
  62.   }
  63.  return st;
  64. }
  65.  
  66. int main()
  67. { int i,ans,a,b,pa,pb;
  68.   cin >> n >> t;
  69.   for(i = 1; i <= n; ++i)
  70.     cin >> v[i];
  71.   sort(v + 1, v + n + 1);
  72.   /*
  73.   for(i = 1; i <= n; ++i)
  74.     cout << v[i] <<' ';
  75.   cout <<'\n';
  76.   */
  77.   for(i = 1; i <= t; ++i)
  78.     {
  79.       cin >> a >> b;
  80.     //  cout << cb_st(a) << ' ' << cb_dr(b) <<"\n";
  81.       pb = cb_dr(b);
  82.       pa = cb_st(a);
  83.       ans = pb - pa + 1;
  84.       if(pb == pa && v[pb] != b && v[pa] != a)
  85.         cout << 0;
  86.       else
  87.         cout << ans;
  88.       cout << '\n';
  89.     //  cout <<"************************\n";
  90.     }
  91.   return 0;
  92. }
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