fork download
copy 
  1. //My first binary_lifting
  2. //https://c...content-available-to-author-only...s.com/edu/course/2/lesson/6/1/practice/contest/283911/problem/D
  3. //Binary lifting is faster then upper_bound and lower_bonud when the dataset is huge.
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. #define int long long
  7. int32_t main()
  8. {
  9. 	int tc,n,i,low,high,m,lift;cin>>n;
  10. 	vector<int>v(n);
  11. 	for(auto &it:v){cin>>it;}
  12. 	sort(v.begin(),v.end());
  13. 	cin>>tc;
  14. 	while(tc--)
  15.     {
  16.         int x=0,y=0,pos_low=0,pos_hi=0;
  17.         cin>>low>>high;lift=0;
  18.  
  19.  
  20.         //Binary lifting of lower_bound
  21.         for(i=25;i>=0;i--)
  22.         {
  23.             lift=(1<<i);
  24.             if(lift+pos_low<n)
  25.             {
  26.                 if(v[lift+pos_low]<low){pos_low+=lift;}
  27.             }
  28.         }if(v[pos_low]<low){pos_low++;}
  29.  
  30.  
  31.         //Binary lifting of upper_bound
  32.         for(i=25;i>=0;i--)
  33.         {
  34.             lift=(1<<i);
  35.             if(lift+pos_hi<n)
  36.             {
  37.                 if(v[lift+pos_hi]<=high){pos_hi+=lift;}
  38.             }
  39.         }if(v[pos_hi]<=high){pos_hi++;}
  40.  
  41.  
  42.         cout<<pos_hi-pos_low<<endl;
  43.     }
  44. }
  45.  
Success #stdin #stdout 0.01s 5536KB
comments (?)
stdin
copy 
5
10 1 10 3 4
4
1 10
2 9
3 4
2 2
stdout
copy 
5
2
2
0
https://ideone.com/6luD4v
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!