fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5.  
  6. const int MOD = 1e9 + 7;
  7.  
  8. void solve(){
  9.  
  10. 	int n, q;
  11. 	cin >> n >> q;
  12.  
  13. 	vector<int> a(n + 1);
  14. 	vector<int>pre(n + 1);
  15. 	set<int> s;
  16. 	map<int, set<int>> p_idx_even, p_idx_odd;
  17. 	for(int i = 1; i <= n; i++){
  18. 		cin >> a[i];
  19. 		if(a[i] != 0)s.insert(i);
  20. 		pre[i] = pre[i - 1] ^ a[i];
  21. 		if(i % 2 == 0)p_idx_even[pre[i]].insert(i);
  22. 		else p_idx_odd[pre[i]].insert(i);
  23.  
  24. 	}
  25.  
  26. 	while(q--){
  27. 		int x, y;
  28. 		cin >> x >> y;
  29. 		auto g = s.lower_bound(x);
  30. 		if(g == s.end() || (*g) > y){
  31. 			cout << 0 << "\n";
  32. 			continue;
  33. 		}
  34. 		if((pre[y] ^ pre[x - 1]) != 0){
  35. 			cout << -1 << "\n";
  36. 		}else{
  37. 			if((y - x + 1) % 2 != 0){
  38. 				cout << 1 << "\n";
  39. 			}else{
  40. 				if(a[x] == 0 || a[y] == 0){
  41. 					cout << 1 <<"\n";
  42. 				}else{
  43. 					if((x - 1) % 2 == 0){
  44. 						auto g = p_idx_odd[pre[x - 1]].lower_bound(x);
  45. 						if(g == p_idx_odd[pre[x - 1]].end() || (*g) > y){
  46.  
  47. 							cout <<  -1 << "\n";
  48. 						}else{
  49. 							cout << 2 << "\n";
  50. 						}
  51. 					}else{
  52. 						auto g = p_idx_even[pre[x - 1]].lower_bound(x);
  53. 						if(g == p_idx_even[pre[x - 1]].end() || (*g) > y){
  54. 							cout << -1 << "\n";
  55. 						}else{
  56. 							cout << 2 << "\n";
  57. 						}
  58. 					}
  59. 				}
  60. 			}
  61. 		}
  62. 	}
  63.  
  64. }
  65.  
  66. int main(){
  67. 	ios_base::sync_with_stdio(false);
  68. 	cin.tie(nullptr);
  69.  
  70. 	int t = 1;
  71. 	// cin >> t;
  72.  
  73. 	for(int i = 1; i <= t; i++){
  74. 		solve();
  75. 	}
  76. 	return 0;
  77. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
7 6
3 0 3 3 1 2 3
3 4
4 6
3 7
5 6
1 6
2 2
stdout
copy 
-1
1
1
-1
2
0
https://ideone.com/s0LGDk
language:
C++14 (gcc 8.3)
created:
2 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!