fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 1e5;
  5. int n, m, pointer, ans[MAXN];
  6. pair<int, int> a[MAXN], q[MAXN];
  7. vector<long long> M, B;
  8.  
  9. bool bad(int l1, int l2, int l3) {
  10. 	return (B[l3] - B[l1]) * (M[l1] - M[l2]) < (B[l2] - B[l1]) * (M[l1] - M[l3]);
  11. }
  12.  
  13. void add(long long m, long long b) {
  14. 	M.push_back(m);
  15. 	B.push_back(b);
  16.  
  17. 	while (M.size() >= 3 && bad(M.size() - 3, M.size() - 2, M.size() - 1)) {
  18. 		M.erase(M.end() - 2);
  19. 		B.erase(B.end() - 2);
  20. 	}
  21. }
  22.  
  23. long long query(long long x) {
  24. 	if (pointer >= M.size()) pointer = M.size() - 1;
  25.  
  26. 	while (pointer < M.size() - 1 && M[pointer + 1] * x + B[pointer + 1] < M[pointer] * x + B[pointer]) pointer++;
  27. 	return M[pointer] * x + B[pointer];
  28. }
  29.  
  30. int main() {
  31. 	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  32.  
  33. 	cin >> n;
  34. 	for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
  35.  
  36. 	sort(a, a + n, greater<pair<int, int>>());
  37. 	int _;
  38. 	cin >> _;
  39.  
  40. 	for (int i = 0; i < n; i++) add(a[i].first, a[i].second);
  41.  
  42. 	for (int i = 1; i <= _; i++) {
  43. 		cin >> q[i].first;
  44. 		q[i].second = i;
  45. 	}
  46. 	sort(q + 1, q + _ + 1);
  47.  
  48. 	for (int i = 1; i <= _; i++) ans[q[i].second] = query(q[i].first);
  49.  
  50. 	for (int i = 1; i <= _; i++) cout << ans[i] << '\n'; 
  51. 	return 0;
  52. }
  53. // covenx hull trick
Runtime error #stdin #stdout 0.01s 5548KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xAi6sG
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!