fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // we can do this using upper bound also -->
  5.  
  6. int leftPart_lastIndex(long long target, vector<long long> &arr){
  7.  
  8. 	int l = 0, r = arr.size()-1;
  9. 	int ans = -1;
  10. 	while(l <= r){
  11. 		long long mid = (l + r)/2;
  12. 		if(arr[mid] < target){
  13. 			ans = mid;
  14. 			l = mid+1;
  15. 		}
  16. 		else {
  17. 			r = mid-1;
  18. 		}
  19. 	}
  20.  
  21. 	return ans+1;
  22.  
  23. }
  24.  
  25. void operations(vector<long long> &queries, vector<long long> &arr){
  26.  
  27. 	int n = arr.size();
  28.  
  29. 	vector<long long> prefix(n+1, 0);
  30. 	for (int i = 1; i <= n; i++){
  31. 		prefix[i] = prefix[i-1] + arr[i-1];
  32. 	}
  33. 	long long tot_sum = prefix[n];
  34.  
  35. 	for (int i = 0; i < queries.size(); i++){
  36.  
  37. 		int g = leftPart_lastIndex(queries[i], arr);
  38. 		long long left_sum = queries[i]*g - prefix[g];
  39. 		long long right_sum = (tot_sum - prefix[g]) - queries[i]*(n-g); // 1 based index
  40.  
  41. 		cout << left_sum + right_sum << endl;
  42. 	}
  43.  
  44. }
  45.  
  46. int main() {
  47. 	// your code goes here
  48. 	int n, q;
  49. 	cin >> n >> q;
  50. 	vector<long long> arr(n);
  51. 	vector<long long> queries(q);
  52. 	for (int i = 0; i < n; i ++){
  53. 		cin >> arr[i];
  54. 	}
  55. 	for (int i = 0; i < q; i ++){
  56. 		cin >> queries[i];
  57. 	}
  58.  
  59. 	operations(queries, arr);
  60.  
  61. 	return 0;
  62. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
5 1
1 3 5 7 9
5
stdout 
12
https://ideone.com/ZfUeYK
language:
C++14 (gcc 8.3)
created:
8 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!