AJMEW-T001: Racer

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

struct linear {
    lli m, c;
    linear(): m(0), c(0) {};
    linear(lli m, lli c): m(m), c(c) {};
    bool operator < (const linear &rhs) const {
        if(m != rhs.m){
            return m < rhs.m;
        }
        return c < rhs.c;
    }
};

typedef pair<linear, lli> pLl;

const int N = 5e4;

vector<linear> cars;
deque<pLl> cht;

lli intersect(linear &a, linear &b){
    lli x = b.c - a.c;
    lli y = a.m - b.m;
    // return (lli)ceil((double)x / y);
    return x / y + !((x < 0) != (y < 0) || (x % y == 0));
}

void chtInsert(linear l){
    // parallel lines: delete old one
    if(!cht.empty() && cht.back().first.m == l.m){
        cht.pop_back();
        chtInsert(l);
        return;
    }
    // old intersection is right or same with new intersection
    while(!cht.empty() && cht.back().second >= intersect(cht.back().first, l)){
        cht.pop_back();
    }
    if(cht.empty()){
        cht.emplace_back(l, 0);
    } else {
        cht.emplace_back(l, intersect(cht.back().first, l));
    }
}

bool comp(const pLl &lhs, const pLl &rhs){
    return lhs.second < rhs.second;
}

int main(){

    int nCars, Q;
    scanf("%d%d", &nCars, &Q);
    for(int i = 1; i <= nCars; ++i){
        lli m, x;
        scanf("%lld%lld", &x, &m);
        cars.emplace_back(m, -m * x);
    }
    sort(cars.begin(), cars.end());
    for(linear l : cars){
        chtInsert(l);
    }
    while(Q--){
        lli x;
        scanf("%lld", &x);
        linear ans = (upper_bound(cht.begin(), cht.end(), pLl(linear(), x), comp) - 1) -> first;
        cout << max((lli)0, ans.m * x + ans.c) << '\n';
    }

    return 0;
}