Guest User

Untitled

a guest
Jan 24th, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.04 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <stdio.h>
  5.  
  6. #define vector std::vector
  7. #define cin std::cin
  8. #define cout std::cout
  9. #define endl std::endl
  10. #define max(a, b) (a)>(b) ? (a):(b)
  11. #define min(a, b) (a)<(b) ? (a):(b)
  12. #define string std::string
  13.  
  14. typedef long long ll;
  15.  
  16. int lower_bound(vector<int> * vec, int val)
  17. {
  18. if((*vec).size() == 1) return 0;
  19. int l = 0, r = (*vec).size() - 1;
  20.  
  21. while(r - l > 1)
  22. {
  23. int mid = (l + r) / 2;
  24.  
  25. if((*vec)[mid] < val) l = mid;
  26. else r = mid-1;
  27. }
  28. if((*vec)[l] < val && (*vec)[l+1] <= val) return l+1;
  29. return l;
  30. }
  31.  
  32. int main()
  33. {
  34. //n - количество элементов в массиве(он упорядочен по неубыванию)
  35. //m - количество запросов
  36.  
  37. int n
  38. cin >> n >> m;
  39. vector<int> v(n);
  40. for(int i = 0; i < n; i++) cin >> v[i];
  41.  
  42. for(; m > 0; m--)
  43. {
  44. int val;
  45. cin >> val;
  46.  
  47. int pos = lower_bound(&v, val);
  48. cout << v[pos] << endl;
  49. }
  50. return 0;
  51. }
Add Comment
Please, Sign In to add comment