mickypinata

AJMEW-T001: Racer

Aug 26th, 2021 (edited)
727
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5.  
  6. struct linear {
  7.     lli m, c;
  8.     linear(): m(0), c(0) {};
  9.     linear(lli m, lli c): m(m), c(c) {};
  10.     bool operator < (const linear &rhs) const {
  11.         if(m != rhs.m){
  12.             return m < rhs.m;
  13.         }
  14.         return c < rhs.c;
  15.     }
  16. };
  17.  
  18. typedef pair<linear, lli> pLl;
  19.  
  20. const int N = 5e4;
  21.  
  22. vector<linear> cars;
  23. deque<pLl> cht;
  24.  
  25. lli intersect(linear &a, linear &b){
  26.     lli x = b.c - a.c;
  27.     lli y = a.m - b.m;
  28.     // return (lli)ceil((double)x / y);
  29.     return x / y + !((x < 0) != (y < 0) || (x % y == 0));
  30. }
  31.  
  32. void chtInsert(linear l){
  33.     // parallel lines: delete old one
  34.     if(!cht.empty() && cht.back().first.m == l.m){
  35.         cht.pop_back();
  36.         chtInsert(l);
  37.         return;
  38.     }
  39.     // old intersection is right or same with new intersection
  40.     while(!cht.empty() && cht.back().second >= intersect(cht.back().first, l)){
  41.         cht.pop_back();
  42.     }
  43.     if(cht.empty()){
  44.         cht.emplace_back(l, 0);
  45.     } else {
  46.         cht.emplace_back(l, intersect(cht.back().first, l));
  47.     }
  48. }
  49.  
  50. bool comp(const pLl &lhs, const pLl &rhs){
  51.     return lhs.second < rhs.second;
  52. }
  53.  
  54. int main(){
  55.  
  56.     int nCars, Q;
  57.     scanf("%d%d", &nCars, &Q);
  58.     for(int i = 1; i <= nCars; ++i){
  59.         lli m, x;
  60.         scanf("%lld%lld", &x, &m);
  61.         cars.emplace_back(m, -m * x);
  62.     }
  63.     sort(cars.begin(), cars.end());
  64.     for(linear l : cars){
  65.         chtInsert(l);
  66.     }
  67.     while(Q--){
  68.         lli x;
  69.         scanf("%lld", &x);
  70.         linear ans = (upper_bound(cht.begin(), cht.end(), pLl(linear(), x), comp) - 1) -> first;
  71.         cout << max((lli)0, ans.m * x + ans.c) << '\n';
  72.     }
  73.  
  74.     return 0;
  75. }
  76.  
RAW Paste Data Copied