Advertisement
Guest User

Untitled

a guest
Nov 22nd, 2014
136
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <fstream>
  4. #include <utility>
  5. #include <cstdio>
  6. #include <string>
  7. #include <vector>
  8. #include <ctime>
  9. #include <queue>
  10. #include <cmath>
  11. #include <map>
  12. #include <set>
  13. #include <iomanip>
  14.  
  15. #define task "file"
  16.  
  17. using namespace std;
  18.  
  19. int n;
  20. vector<pair<double, int> > a;
  21.  
  22. int BS(double x){
  23.     int l = -1, r = n;
  24.     while(r - l > 1){
  25.         int m = (r + l) / 2;
  26.         if(a[m].first > x)
  27.             r = m;
  28.         else
  29.             l = m;
  30.     }
  31.     return l;
  32. }
  33.  
  34. int main(){
  35.     //ios::syncs_with_stdio(false);
  36.  
  37.     freopen("input.txt", "r", stdin);
  38.     freopen("output.txt", "w", stdout);
  39.     cout << setprecision(3);
  40.  
  41.     int q;
  42.     cin >> n;
  43.     for(int i = 0; i < n; i++){
  44.         int dop;
  45.         double dop1;
  46.         cin >> dop >> dop1;
  47.         a.push_back(make_pair(dop1, dop));
  48.     }
  49.     sort(a.begin(), a.end());
  50.     int k = 0;
  51.     for(int i = n - 1; i >= 0; i --){
  52.         k += a[i].second;
  53.         a[i].second = k;
  54.     }
  55.    
  56.     cin >> q;
  57.     //vector<double> b(q);
  58.     for(int i = 0; i < q; i++){
  59.         double dop;
  60.         cin >> dop;
  61.         //b.push_back(dop);
  62.         int low = BS(dop) + 1;
  63.         cout << a[low].second << endl;
  64.     }
  65.    
  66.     return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement