fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll  long long
  6. #define ld  double
  7.  
  8. #define all(x)  x.begin(), x.end()
  9. #define ii      pair<int, int>
  10.  
  11. #define pb  push_back
  12. #define X   first
  13. #define Y   second
  14.  
  15. const int   inf = 1e9;
  16. const int   mod = 1e9 + 7;
  17. const int   N   = 1e5 + 5;
  18.  
  19. void file(){
  20.   freopen("baoloi.inp", "r", stdin);
  21.   freopen("baoloi.out", "w", stdout);
  22. }
  23.  
  24. int n, qr;
  25. ii a[N];
  26. vector<int> q;
  27.  
  28. bool bad(int l1, int l2, int l3){
  29.   return 1ll * (a[l3].Y - a[l1].Y) * (a[l1].X - a[l2].X) < 1ll * (a[l2].Y - a[l1].Y) * (a[l1].X - a[l3].X);
  30. }
  31.  
  32. void addLine(int i){
  33.   if(q.size() < 2) q.pb(i);
  34.   else{
  35.     while(q.size() >= 2 && bad(q[(int)q.size() - 2], q.back(), i)) q.pop_back();
  36.     q.pb(i);
  37.   }
  38. }
  39.  
  40. ll solve(int x){
  41.   int l = 1, r = q.size() - 1, pos = 0;
  42.   while(l <= r){
  43.     int mid = (l + r) / 2;
  44.     if(1ll * a[q[mid]].X * x + a[q[mid]].Y > 1ll * a[q[mid - 1]].X * x + a[q[mid - 1]].Y){
  45.       r = mid - 1;
  46.     }
  47.     else{
  48.       pos = mid;
  49.       l = mid + 1;
  50.     }
  51.   }
  52.   return 1ll * a[q[pos]].X * x + a[q[pos]].Y;
  53. }
  54.  
  55. int main(){
  56.   cin.tie(0) -> sync_with_stdio(0);
  57.   file();
  58.   cin >> n >> qr;
  59.   for(int i = 1; i <= n; ++i){
  60.     cin >> a[i].X >> a[i].Y;
  61.   }
  62.   sort(a + 1, a + n + 1, [&](ii x, ii y){return x.X > y.X;});
  63.   for(int i = 1; i <= n; ++i){
  64.     addLine(i);
  65.   }
  66.   int pointer = 0;
  67.   for(int i = 1; i <= qr; ++i){
  68.     int x; cin >> x;
  69.     cout << solve(x) << '\n';
  70.   }
  71.   return 0;
  72. }
  73.  
Success #stdin #stdout 0s 5532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kTqTKM
language:
C++14 (gcc 8.3)
created:
1 year 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!