fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MaxN=2e5+1;
  5. long int arr[MaxN];
  6. long int pS[MaxN];
  7. int main() {
  8. 	long int N,Q;
  9. 	cin >> N>>Q;
  10. 	pS[0]=0;
  11. 	for(int i=1;i<=N;i++){
  12. 		cin >> arr[i];
  13. 		pS[i]=pS[i-1]+arr[i];
  14. 		//cout << pS[i] << ' ';
  15. 	}
  16. 	int l,r;
  17. 	while(Q--){
  18. 		cin>>l>>r;
  19. 		long int num=pS[r]-pS[l-1];
  20. 		if(num==0){
  21. 			cout << -1 << '\n';
  22. 			return 0;
  23. 		}else if(num%2==1){
  24. 			num=num+1;
  25. 			num/=2;
  26. 			long int cnt=0;
  27. 			for(int i=l;i<=r;i++){
  28. 				cnt+=arr[i];
  29. 				if(cnt>=num){
  30. 					cout << i << '\n';
  31. 					return 0;
  32. 				}
  33. 			}
  34. 		}else{
  35. 			long int num1=num/2;
  36. 			long int num2=num/2+1;
  37. 			//cout << num1 << ' ' << num2 << '\n';
  38. 			long int cnt=0;
  39. 			for(int i=l;i<=r;i++){
  40. 				cnt+=arr[i];
  41. 				if(cnt>=num1){
  42. 					num1=i;
  43. 					break;
  44. 				}
  45. 			}
  46. 			cnt=0;
  47. 			for(int i=l;i<=r;i++){
  48. 				cnt+=arr[i];
  49. 				if(cnt>=num2){
  50. 					num2=i;
  51. 					break;
  52. 				}
  53. 			}
  54. 			//cout << num1 << ' '<< num2 << '\n';
  55. 			cout << (num1+num2)/2 << '\n';
  56. 			return 0;
  57. 		}
  58. 	}
  59. }
Success #stdin #stdout 0s 5536KB
comments (?)
stdin
copy 
5 2
2 1 0 0 3
1 5
1 3
stdout
copy 
3 4
2 5
3
https://ideone.com/814J8t
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!