SHARE
TWEET

Untitled

a guest Feb 20th, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define pii pair<int, int>
  5.  
  6. using namespace std;
  7.  
  8. int main()
  9. {
  10.     int n, m, k;
  11.     cin >> n >> m;
  12.     k = (int)sqrt(n + 0.) + 1;
  13.     vector<int> data(n), res(m);
  14.     vector<vector<int> > block(k);
  15.  
  16.     for(int i = 0; i < n; i++)
  17.     {
  18.         cin >> data[i];
  19.         block[i/k].push_back(data[i]);
  20.     }
  21.  
  22.     for(int i = 0; i < k; i++)
  23.         sort(block[i].begin(), block[i].end());
  24.  
  25.     for(int i = 0; i < m; i++)
  26.     {
  27.         int l, r, _min, _max;
  28.         cin >> l >> r >> _min >> _max;
  29.         l--;
  30.         r--;
  31.  
  32.         int j = l;
  33.         int ans = 0;
  34.         while(j <= r)
  35.         {
  36.             if(j%k == 0 && j + k - 1 <= r)
  37.             {
  38.                 ans += upper_bound(block[j/k].begin(), block[j/k].end(), _max)
  39.                      - lower_bound(block[j/k].begin(), block[j/k].end(), _min);
  40.                 j += k;
  41.             }
  42.             else
  43.             {
  44.                 if(_min <= data[j] && data[j] <= _max)
  45.                     ans++;
  46.                 j++;
  47.             }
  48.         }
  49.         res[i] = ans;
  50.     }
  51.     for(int i = 0; i < res.size(); i++)
  52.         cout << res[i] << endl;
  53.     return 0;
  54. }
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