結果

問題 No.704 ゴミ拾い Medium
コンテスト
ユーザー Pachicobue
提出日時 2019-02-14 20:01:34
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 544 ms / 1,500 ms
コード長 9,081 bytes
コンパイル時間 1,793 ms
コンパイル使用メモリ 135,428 KB
最終ジャッジ日時 2025-01-06 21:09:35
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <limits>
#include <random>
using ll = long long;
template <typename T>
constexpr T INF() { return std::numeric_limits<T>::max() / 16; }
template <typename T, typename V = T>
class LiChaoTree
{
    static std::size_t SZ(const std::size_t n)
    {
        std::size_t ans = 1;
        for (; ans < n; ans <<= 1) {}
        return ans;
    }

public:
    template <typename InIt>
    LiChaoTree(const InIt first, const InIt last)
        : size(std::distance(first, last)), half(SZ(size)), x(size), seg(half << 1, Line{0, 0, true}) { std::copy(first, last, x.begin()); }
    void add(const T a, const T b, const std::size_t lind, const std::size_t rind)
    {
        const Line line{a, b, false};
        for (std::size_t L = lind + half, R = rind + half, sz = 1, left = lind, right = rind; L < R; L >>= 1, R >>= 1, sz <<= 1) {
            if (L & 1) { addLine(line, L++, left, left + sz), left += sz; }
            if (R & 1) { right -= sz, addLine(line, --R, right, right + sz); }
        }
    }
    std::pair<bool, V> query(std::size_t ind) const
    {
        bool exist = false;
        V ans = INF<V>();
        const T X = x[ind];
        for (ind += half; ind > 0; ind >>= 1) {
            if (not seg[ind].null) { ans = (exist ? std::min(ans, seg[ind].val(X)) : seg[ind].val(X)), exist = true; }
        }
        return {exist, ans};
    }

private:
    struct Line
    {
        T a, b;
        bool null = true;
        T val(const T x) const { return a * x + b; }
    };

    void addLine(Line l, const std::size_t ind, const std::size_t L, const std::size_t R)
    {
        const std::size_t M = (L + R) / 2;
        if (seg[ind].null) { return (void)(seg[ind] = l); }
        const T lx = x[L], rx = x[R - 1], mx = x[M];
        const bool lunder = l.val(lx) < seg[ind].val(lx), munder = l.val(mx) < seg[ind].val(mx), runder = l.val(rx) < seg[ind].val(rx);
        if (lunder and runder) { return (void)(seg[ind] = l); }
        if (not lunder and not runder) { return; }
        if (munder) { std::swap(seg[ind], l); }
        return lunder != munder ? addLine(l, ind << 1, L, M) : addLine(l, ind << 1 | 1, M, R);
    }

    std::size_t size, half;
    std::vector<T> x;
    std::vector<Line> seg;
};
template <typename Base>
class LazySeg
{
    static std::size_t SZ(const std::size_t n)
    {
        std::size_t ans = 1;
        for (; ans < n; ans <<= 1) {}
        return ans;
    }

public:
    using BaseAlgebra = Base;
    using ValMonoid = typename BaseAlgebra::ValMonoid;
    using OpMonoid = typename BaseAlgebra::OpMonoid;
    using T = typename BaseAlgebra::VT;
    using F = typename BaseAlgebra::OT;
    LazySeg(const std::size_t n) : size(n), half(SZ(n)), value(half << 1, ValMonoid::id()), action(half << 1, OpMonoid::id()) {}
    template <typename InIt>
    LazySeg(const InIt first, const InIt last) : size(distance(first, last)), half(SZ(size)), value(half << 1, ValMonoid::id()), action(half << 1, OpMonoid::id())
    {
        copy(first, last, value.begin() + half);
        for (std::size_t i = half - 1; i >= 1; i--) { up(i); }
    }
    T get(const std::size_t a) const { return accumulate(a, a + 1); }
    void set(std::size_t a, const T& val)
    {
        modify(a, a + 1, OpMonoid::id()), value[a += half] = val;
        while (a >>= 1) { up(a); }
    }
    T accumulate(const std::size_t L, const std::size_t R) const
    {
        auto arec = [&](auto&& self, const std::size_t index, const std::size_t left, const std::size_t right) -> T {
            if (L <= left and right <= R) {
                return value[index];
            } else if (right <= L or R <= left) {
                return ValMonoid::id();
            } else {
                return act(action[index], acc(self(self, index << 1, left, (left + right) >> 1), self(self, index << 1 | 1, (left + right) >> 1, right)));
            }
        };
        return arec(arec, 1, 0, half);
    }
    void modify(const std::size_t L, const std::size_t R, const F& f)
    {
        auto mrec = [&](auto&& self, const std::size_t index, const std::size_t left, const std::size_t right) -> void {
            if (L <= left and right <= R) {
                this->update(index, f);
            } else if (right <= L or R <= left) {
            } else {
                this->update(index << 1, action[index]), this->update(index << 1 | 1, action[index]);
                self(self, index << 1, left, (left + right) >> 1), self(self, index << 1 | 1, (left + right) >> 1, right);
                this->up(index), action[index] = OpMonoid::id();
            }
        };
        mrec(mrec, 1, 0, half);
    }
    std::vector<T> data() const
    {
        std::vector<T> ans(size);
        for (std::size_t i = 0; i < size; i++) { ans[i] = get(i); }
        return ans;
    }

private:
    void up(const std::size_t i) { value[i] = acc(value[i << 1], value[i << 1 | 1]); }
    void update(const std::size_t i, const F& f) { value[i] = act(f, value[i]), action[i] = compose(f, action[i]); }
    const std::size_t size, half;
    std::vector<T> value;
    std::vector<F> action;
    const ValMonoid acc{};
    const OpMonoid compose{};
    const BaseAlgebra act{};
};

template <typename T>
std::ostream& operator<<(std::ostream& os, const LazySeg<T>& seg)
{
    os << "[";
    for (const auto& e : seg.data()) { os << e << ","; }
    return (os << "]" << std::endl);
}
using ll = long long;
std::mt19937 mt{std::random_device{}()};
template <typename VX = ll, typename OX = ll>
struct Sum_Plus
{
    using VT = std::pair<VX, VX>;
    struct ValMonoid
    {
        VT operator()(const VT& a, const VT& b) const { return {a.first + b.first, a.second + b.second}; }
        static constexpr VT id() { return {0, 0}; }
    };
    using OT = OX;
    struct OpMonoid
    {
        OT operator()(const OT& f1, const OT& f2) const { return f1 + f2; }
        static constexpr OT id() { return 0; }
    };
    VT operator()(const OT& f, const VT& x) const { return {x.first + x.second * f, x.second}; }
};
void CodeChef()
{
    ll N;
    std::size_t M;
    std::cin >> N >> M;
    std::set<ll> xs;
    struct Q
    {
        std::size_t t;
        ll u = 0, v = 0, a = 0, b = 0;
    };
    std::vector<Q> query(M);
    for (std::size_t i = 0; i < M; i++) {
        std::cin >> query[i].t;
        if (query[i].t == 3) {
            std::cin >> query[i].u, xs.insert(query[i].u - 1), xs.insert(query[i].u), xs.insert(query[i].u + 1);
        } else {
            std::cin >> query[i].u >> query[i].v >> query[i].a >> query[i].b, xs.insert(query[i].u - 1), xs.insert(query[i].u), xs.insert(query[i].u + 1), xs.insert(query[i].v - 1), xs.insert(query[i].v), xs.insert(query[i].v + 1);
        }
    }
    std::map<ll, std::size_t> zip;
    std::size_t cnt = 0;
    std::vector<typename Sum_Plus<ll, ll>::VT> v(xs.size());
    for (const ll z : xs) { v[cnt].second = z, zip[z] = cnt++; }
    for (std::size_t i = 0; i < xs.size(); i++) { v[i].second = (i == xs.size() - 1 ? 1LL : v[i + 1].second - v[i].second); }
    LiChaoTree<ll> cht(xs.begin(), xs.end());
    LazySeg<Sum_Plus<ll, ll>> seg(v.begin(), v.end());
    for (const auto& q : query) {
        if (q.t == 1) {
            const ll a = q.a;
            const ll b = q.b - a * q.u;
            cht.add(-a, -b, zip[q.u], zip[q.v] + 1);
        } else if (q.t == 2) {
            const std::size_t u = zip[q.u], v = zip[q.v];
            seg.modify(u, u + 1, q.b);
            if (u < v) { seg.modify(u + 1, v + 1, q.a); }
        } else {
            const std::size_t u = zip[q.u];
            const ll fee = seg.accumulate(0, u + 1).first;
            const auto info = cht.query(u);
            if (not info.first) {
                std::cout << "NA" << std::endl;
            } else {
                std::cout << fee - info.second << std::endl;
            }
        }
    }
}

void yukicoder()
{
    std::size_t N;
    std::cin >> N;
    std::vector<ll> a(N + 1), x(N + 1), y(N + 1);
    std::vector<ll> X;
    for (std::size_t i = 1; i <= N; i++) { std::cin >> a[i], X.push_back(a[i]); }
    for (std::size_t i = 1; i <= N; i++) { std::cin >> x[i], X.push_back(x[i]); }
    for (std::size_t i = 1; i <= N; i++) { std::cin >> y[i]; }
    std::sort(X.begin(), X.end());
    X.erase(std::unique(X.begin(), X.end()), X.end());
    std::map<ll, std::size_t> zip;
    for (std::size_t i = 0; i < X.size(); i++) { zip[X[i]] = i; }
    LiChaoTree<ll> cht(X.begin(), X.end());
    std::vector<ll> dp(N + 1);
    dp[0] = 0;
    cht.add(1, -x[1] + std::abs(y[1]) + dp[0], zip[x[1]], X.size());
    cht.add(-1, x[1] + std::abs(y[1]) + dp[0], 0, zip[x[1]]);
    for (std::size_t i = 1; i <= N; i++) {
        dp[i] = cht.query(zip[a[i]]).second;
        if (i < N) {
            cht.add(1, -x[i + 1] + std::abs(y[i + 1]) + dp[i], zip[x[i + 1]], X.size());
            cht.add(-1, x[i + 1] + std::abs(y[i + 1]) + dp[i], 0, zip[x[i + 1]]);
        }
    }
    std::cout << dp[N] << std::endl;
}

int main()
{
    yukicoder();
    return 0;
}
0