P9368 [ICPC2022 Xi'an] Streets

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <iostream>
#include <ostream>
#include <vector>
using i64         = long long;
using vi          = std::vector<int>;
constexpr int NM  = 5e3 + 5;
constexpr int V   = 1e5 + 5;
constexpr int inf = 1e9;

int n, m, T;
i64 C;
int x[NM], y[NM], a[NM], b[NM];
int vdx[V], vdy[V];
int root{-1};

int stp = -1;
vi stack, tstack;
vi popped[V];

bool left_side(int i, int j, int k) {
    assert(i <= j && j <= k);
    int xs = j - k;
    int ys = vdx[j] - vdx[k];
    int xx = i - k;
    int yx = vdx[i] - vdx[k];
    return 1ll * xs * yx >= 1ll * ys * xx;
}

i64 cost(int dx, int dy) { return 1ll * dx * vdy[dy] + 1ll * dy * vdx[dx]; }

std::ostream &operator<<(std::ostream &os, vi &v) {
    os << "[";
    for (auto x : v) os << x << ',';
    os << "]" << '\n';
    return os;
}

int main() {
    std::cin >> n >> m >> T;
    for (int i = 1; i <= n; i++) std::cin >> x[i];
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    for (int i = 1; i <= m; i++) std::cin >> y[i];
    for (int i = 1; i <= m; i++) std::cin >> b[i];
    for (int i = 0; i < V; i++) vdx[i] = vdy[i] = inf;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++) vdx[x[j] - x[i]] = std::min(vdx[x[j] - x[i]], a[j] + a[i]);
    for (int i = 1; i <= m; i++)
        for (int j = i; j <= m; j++) vdy[y[j] - y[i]] = std::min(vdy[y[j] - y[i]], b[j] + b[i]);

    for (int dx = V - 1; dx >= 0; dx--) {
        if (vdx[dx] == inf) continue;
        while (stp >= 1 && left_side(dx, stack[stp], stack[stp - 1])) {
            popped[dx].push_back(stack.back());
            stack.pop_back();
            stp--;
        }
        if (root == -1) root = dx;
        stack.push_back(dx);
        stp++;
    }

    tstack.resize(stack.size());
    std::copy(stack.begin(), stack.end(), tstack.begin());

    while (T--) {
        std::cin >> C;
        int now_dx = 0;
        i64 ans    = 0;
        stack.clear();
        for (auto v : tstack) stack.push_back(v);

        auto next = [&] {
            if (now_dx > root) return;
            
            // 维护凸包，先弹掉顶部的点
            assert(stack.back() == now_dx && "stack not match");
            stack.pop_back();
            // 再加入点
            for (auto it = popped[now_dx].rbegin(); it != popped[now_dx].rend(); it++) 
                stack.push_back(*it);

            now_dx++; // 移动到下一个可以得到的 dx
            while (now_dx <= root && vdx[now_dx] == inf) now_dx++;
            
            if (now_dx <= root) 
                assert(stack.back() == now_dx && "stack not match after next()");
        };

        // 二分，判断是否有点 x, f(x) 在直线下方，且 x >= dx.
        auto BS = [&](int dx, int dy) {
            if (dx == 0) return true;
            std::reverse(stack.begin(), stack.end());
            stack.push_back(V - 1);
            int l = -1, r = stack.size() - 1;
            while (l + 1 < r) {
                int mid = l + ((r - l) >> 1);
                int middx = stack[mid];
                int nxtdx = stack[mid + 1];
                if (cost(middx, dy) > cost(nxtdx, dy)) l = mid;
                else r = mid;
            }
            bool res = cost(stack[r], dy) <= C;
            stack.pop_back();
            std::reverse(stack.begin(), stack.end());
            return res;
        };

        for (int dy = V - 1; dy >= 1 && now_dx <= root; dy--) {
            if (vdy[dy] == inf) continue; // 跳过无法取到的 dy.
            // std::fprintf(stderr, "dy=%d, now_dx=%d\n", dy, now_dx);
            while (now_dx <= root && BS(now_dx, dy))  {
                ans = std::max(ans, 1ll * dy * now_dx);
                next();
            }
        }

        std::cout << ans << '\n';
    }
}