fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long double ld;
  6. typedef long long lli;
  7. typedef pair<lli, lli> ii;
  8. typedef vector<lli> vi;
  9.  
  10. #define endl '\n'
  11. #define f first
  12. #define s second
  13. #define pb push_back
  14. #define sz(s) lli(s.size())
  15. #define all(s) begin(s), end(s)
  16. #define fore(i, a, b) for(lli i = (a), TT = (b); i < TT; ++i)
  17. #define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  18.  
  19. lli n, k, aux;
  20. vi v;
  21.  
  22. bool f(lli pos, lli x){
  23. 	if(pos>n+1) return false;
  24.  
  25. 	return v[pos] < x;
  26. }
  27.  
  28. int main() { 	
  29. 	cin >> n;
  30. 	for(lli i=0; i<n; i++){
  31. 		cin >> aux;
  32. 		v.pb(aux);
  33. 	}
  34.  
  35. 	v.pb(-1e10);
  36. 	v.pb(1e10);
  37.  
  38. 	sort(all(v));
  39.  
  40. 	cin >> k;
  41.  
  42. 	while(k--){
  43. 		lli l, r;
  44. 		cin >> l >> r;
  45.  
  46.  
  47. 		lli pos1 = 0;
  48. 		lli pow = log2(n+2)+1;
  49. 		for(lli i = pow; i>=0;i--){
  50. 			lli paso = 1ll<<i;
  51. 			if(f(paso+pos1, l)){
  52. 				pos1+=paso;
  53. 			}
  54. 		}
  55.  
  56. 		lli pos2 = 0;
  57. 		pow = log2(n+2)+1;
  58. 		for(lli i = pow; i>=0;i--){
  59. 			lli paso = 1ll<<i;
  60. 			if(f(paso+pos2, r+1)){
  61. 				pos2+=paso;
  62. 			}
  63. 		}
  64.  
  65. 		cout << pos2-pos1 << " ";
  66. 	}
  67.  
  68.     return 0;
  69. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Bm7o1U
language:
C++14 (gcc 8.3)
created:
7 hours 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!