fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main(int argc, char** argv) {
  4.  
  5. 	ios_base::sync_with_stdio(false);
  6. 	cin.tie(NULL);
  7. 	cout.tie(NULL);
  8. 	int N,Q;
  9. 	cin>>N>>Q;
  10. 	vector<int> a(N);
  11. 	vector<vector<int>> d(31);
  12. 	for (int i=0;i<N;i++){
  13.  
  14. 		cin>>a[i];
  15. 		int p = 1;
  16. 		for (int j=0;j<30;j++){
  17. 			if ((a[i]>=p) and (a[i] < p*2)){
  18. 				d[j].push_back(i);
  19. 				break;
  20. 			}
  21. 			p=p*2;
  22. 		}	
  23. 	}
  24.  
  25. /*	for (int i=0;i<30;i++){
  26. 		cout<<pow(2,i)<<" - "<<pow(2,i+1)-1<<": ";
  27. 		for (int j = 0;j < d[i].size();j++){
  28. 			cout<<d[i][j]<<' ';
  29. 		}
  30. 		cout<<'\n';
  31. 	}
  32.  
  33. 	cout<<"UPITI\n";  */
  34. 	while(Q--){
  35.  
  36. 		int L,R;
  37. 		cin>>L>>R;
  38. 		L--; R--;
  39. 		int rez=-1;
  40. 		for (int i = 0;i<30;i++){
  41. 			if (d[i].size()==0) continue;
  42. 			int l = distance(d[i].begin(),lower_bound(d[i].begin(),d[i].end(),L));
  43. 			int r = distance(d[i].begin(),upper_bound(d[i].begin(),d[i].end(),R)) - 1;
  44. 		//	cout<<l<<" "<<r<<"   "<<r-l+1<<'\n';
  45. 			if (r-l+1>rez){
  46. 				rez = r-l+1;
  47. 			}
  48. 		}
  49. 		cout<<max(rez,1)<<'\n';
  50. 	}
  51.  
  52.  
  53. 	return 0;
  54. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5 3
1 2 1 3 2
1 5
1 4
2 3
stdout
copy 
3
2
1
https://ideone.com/VszZNj
language:
C++14 (gcc 8.3)
created:
4 days 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!