fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. ll n,q;
  5. ll arr[100001];
  6. vector<vector<ll>>prefixSum;
  7.  
  8. void preCompute(){
  9. 	for(ll i=1;i<=n;i++){
  10. 		for(ll j=0;j<=31;j++){
  11. 			prefixSum[j][i] = prefixSum[j][i-1] + ((arr[i]&(1<<j))?1:0); 
  12. 		}
  13. 	}
  14.  
  15. 	// for(ll i=0;i<=31;i++){
  16. 	// 	for(ll j=1;j<=n;j++){
  17. 	// 		cout<<prefixSum[i][j]<<" ";
  18. 	// 	}
  19. 	// 	cout<<endl;
  20. 	// }
  21. }
  22.  
  23. vector<ll> solve(ll queries[][4],ll arr[] ,ll n , ll q){
  24. 	vector<ll>ans(q);
  25. 	for(ll i=0;i<q;i++){
  26. 		ll l1 = queries[i][0];
  27. 		ll r1 = queries[i][1];
  28. 		ll l2 = queries[i][2];
  29. 		ll r2 = queries[i][3];
  30. 		// ll and1=-1,and2=-1,xor1=0;
  31.  
  32. 		// working on query 1 first
  33. 		ll diff1 = r1-l1+1;
  34. 		ll a=0;
  35. 		for(ll j=0;j<=31;j++){
  36. 			if(diff1 == prefixSum[j][r1] - prefixSum[j][l1-1]){
  37. 				a += (1<<j);
  38. 			}
  39. 		}
  40.  
  41. 		// working on query 2 
  42. 		ll diff2 = r2-l2+1;
  43. 		ll b=0;
  44. 		for(ll j=0;j<=31;j++){
  45. 			if(diff2 == prefixSum[j][r2] - prefixSum[j][l2-1]){
  46. 				b += (1<<j);
  47. 			}
  48. 		}
  49. 		ans[i] = a^b;
  50. 	}
  51. 	return ans;
  52. }
  53.  
  54. int main() {
  55. 	ios::sync_with_stdio(false);
  56. 	cin.tie(0);
  57.  
  58. 	cin>>n;
  59.  
  60. 	for(int i=1;i<=n;i++){
  61. 		cin>>arr[i];
  62. 	}
  63. 	cin>>q;
  64. 	ll queries[q][4];
  65. 	for(int i=0;i<q;i++){
  66. 		for(int j=0;j<4;j++){
  67. 			cin>>queries[i][j];
  68. 		}
  69. 	}
  70. 	prefixSum.assign(32, vector<ll>(n + 1, 0));
  71. 	preCompute();
  72. 	vector<ll>ans = solve(queries,arr,n,q);
  73.  
  74. 	for(int x:ans)cout<<x<<" ";
  75.  
  76. 	return 0;
  77. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
9
8 6 5 9 7 7 9 3 8 
1
3 5 5 5
stdout
copy 
6
https://ideone.com/Juzujw
language:
C++ (gcc 8.3)
created:
7 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!