fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. 	// your code goes here
  6.  
  7. 	vector<int> price = {2,5,1};
  8. 	vector<int> query = {8,4,3}; //ans: 16,6,5
  9.  
  10. 	// vector<int> price = {1,2,3};
  11. 	// vector<int> query = {3,2,1,5}; //ans: 3,2,3,9
  12.  
  13. 	int n = price.size();
  14.  
  15.     vector<int> ans(query.size(),0);
  16.  
  17.     // sort
  18.     sort(price.begin(), price.end());
  19.  
  20.     // prefix:-
  21.     vector<int> p(n,0);
  22.     p[0] = price[0];
  23.     for(int i=1; i<n; i++){
  24.     	p[i] = p[i-1] + price[i];
  25.     }
  26.  
  27.     for(int i=0; i<query.size(); i++){
  28.  
  29.         auto it = lower_bound(price.begin(), price.end(), query[i]);
  30.  
  31.         int id = it - price.begin();
  32.  
  33.         cout<< "found id="<<id<<"for query[i]=" << query[i]<<endl;
  34.  
  35.         //for <id
  36.         ans[i] = query[i]*id - p[id-1];
  37.  
  38.         //for >= id
  39.         ans[i] += p[n-1]-p[id-1] - (n-id)*query[i];
  40. 	    cout<< ans[i]<< endl;
  41.     }
  42.  
  43.     return 0;
  44.  
  45. }
  46.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
5 3 3
1 2 3 4 5
5 4 3 2 1
stdout
copy 
found id=3for query[i]=8
16
found id=2for query[i]=4
6
found id=2for query[i]=3
5
https://ideone.com/y5jtN0
language:
C++14 (gcc 8.3)
created:
19 hours 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!