Merevoli

Trick

Dec 4th, 2021
709
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. int pointer;
  2. vector < long long > M, B;
  3. bool bad(int l1, int l2, int l3) {
  4.     return (B[l3] - B[l1]) * (M[l1] - M[l2]) < (B[l2] - B[l1]) * (M[l1] - M[l3]);
  5. }
  6. void add(long long m, long long b) {
  7.     M.push_back(m);
  8.     B.push_back(b);
  9.     while (M.size() >= 3 && bad(M.size() - 3, M.size() - 2, M.size() - 1)) {
  10.         M.erase(M.end() - 2);
  11.         B.erase(B.end() - 2);
  12.     }
  13. }
  14. long long query(long long x) {
  15.     if (pointer >= M.size()) pointer = M.size() - 1;
  16.     while (pointer < M.size() - 1 && M[pointer + 1] * x + B[pointer + 1] > M[pointer] * x + B[pointer])
  17.         pointer++;
  18.     return M[pointer] * x + B[pointer];
  19. }
RAW Paste Data