fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. long long getLastIndex(vector<long long> &price, long long target){
  6. 	int n = price.size();
  7. 	long long low = 0, high = n - 1;
  8. 	long long ans = -1;
  9. 	while(low <= high){
  10. 		long long mid = (low + high) / 2;
  11. 		if(price[mid] <= target){ 
  12. 			ans = mid;           
  13. 			low = mid + 1;       
  14. 		}
  15. 		else{
  16. 			high = mid - 1;
  17. 		}
  18. 	}
  19. 	return ans;
  20. }
  21.  
  22. int main() {
  23. 	long long n, q, target;
  24. 	cin >> n >> q >> target; 
  25. 	vector<long long> queries;
  26. 	vector<long long> price;
  27. 	long long totalSum = 0;
  28.  
  29. 	for(long long i = 0; i < n; i++){
  30. 		long long element;
  31. 		cin >> element;
  32. 		price.push_back(element);
  33. 		totalSum += element;
  34. 	}
  35. 	for(long long i = 0; i < q; i++){
  36. 		long long query;
  37. 		cin >> query;
  38. 		queries.push_back(query);
  39. 	}
  40.  
  41. 	vector<long long> prefixSum(n + 1, 0);
  42. 	sort(price.begin(), price.end());
  43.  
  44. 	for(long long i = 0; i < n; i++)
  45. 		prefixSum[i + 1] = prefixSum[i] + price[i];
  46.  
  47. 	for(long long i = 0; i < q; i++){
  48. 		long long currentTarget = queries[i];
  49. 		long long largestIndexLessThanTarget = getLastIndex(price, currentTarget);
  50.  
  51. 		long long leftPartSum = 0;
  52. 		long long rightPartSum = 0;
  53.  
  54. 		if(largestIndexLessThanTarget >= 0)
  55. 			leftPartSum = currentTarget * (largestIndexLessThanTarget + 1) - prefixSum[largestIndexLessThanTarget + 1];
  56. 		else
  57. 			leftPartSum = 0;
  58.  
  59. 		if(largestIndexLessThanTarget < n - 1)
  60. 			rightPartSum = totalSum - prefixSum[largestIndexLessThanTarget + 1] - currentTarget * (n - 1 - largestIndexLessThanTarget);
  61. 		else
  62. 			rightPartSum = 0;
  63.  
  64. 		long long answer = leftPartSum + rightPartSum;
  65. 		cout << answer<<"\n";
  66. 	}
  67. 	return 0;
  68. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5 3 0
1 3 5 7 9
4 6 8
stdout
copy 
13
13
17
https://ideone.com/YH2gzX
language:
C++ (gcc 8.3)
created:
6 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!