結果

問題 No.2332 Make a Sequence
ユーザー Ricky_ponRicky_pon
提出日時 2023-05-28 15:16:26
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 164 ms / 2,000 ms
コード長 6,382 bytes
コンパイル時間 2,799 ms
コンパイル使用メモリ 164,348 KB
実行使用メモリ 24,236 KB
最終ジャッジ日時 2023-08-27 11:47:41
合計ジャッジ時間 14,616 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 95 ms
19,740 KB
testcase_08 AC 28 ms
5,352 KB
testcase_09 AC 74 ms
13,544 KB
testcase_10 AC 79 ms
18,500 KB
testcase_11 AC 54 ms
11,632 KB
testcase_12 AC 115 ms
23,648 KB
testcase_13 AC 114 ms
23,172 KB
testcase_14 AC 115 ms
23,420 KB
testcase_15 AC 114 ms
23,020 KB
testcase_16 AC 114 ms
23,528 KB
testcase_17 AC 114 ms
24,084 KB
testcase_18 AC 115 ms
24,236 KB
testcase_19 AC 113 ms
23,196 KB
testcase_20 AC 114 ms
23,216 KB
testcase_21 AC 114 ms
23,404 KB
testcase_22 AC 114 ms
23,212 KB
testcase_23 AC 114 ms
23,344 KB
testcase_24 AC 114 ms
23,328 KB
testcase_25 AC 115 ms
22,996 KB
testcase_26 AC 114 ms
22,940 KB
testcase_27 AC 115 ms
23,524 KB
testcase_28 AC 115 ms
22,884 KB
testcase_29 AC 115 ms
23,532 KB
testcase_30 AC 115 ms
23,400 KB
testcase_31 AC 115 ms
23,524 KB
testcase_32 AC 119 ms
22,996 KB
testcase_33 AC 119 ms
23,680 KB
testcase_34 AC 118 ms
23,332 KB
testcase_35 AC 119 ms
23,168 KB
testcase_36 AC 118 ms
23,140 KB
testcase_37 AC 118 ms
23,220 KB
testcase_38 AC 118 ms
23,300 KB
testcase_39 AC 120 ms
23,720 KB
testcase_40 AC 118 ms
23,428 KB
testcase_41 AC 119 ms
24,128 KB
testcase_42 AC 133 ms
23,800 KB
testcase_43 AC 132 ms
23,524 KB
testcase_44 AC 130 ms
23,768 KB
testcase_45 AC 134 ms
22,884 KB
testcase_46 AC 133 ms
23,272 KB
testcase_47 AC 164 ms
23,192 KB
testcase_48 AC 163 ms
23,396 KB
testcase_49 AC 163 ms
23,452 KB
testcase_50 AC 164 ms
23,476 KB
testcase_51 AC 164 ms
23,296 KB
testcase_52 AC 116 ms
23,000 KB
testcase_53 AC 116 ms
23,468 KB
testcase_54 AC 116 ms
23,152 KB
testcase_55 AC 116 ms
23,816 KB
testcase_56 AC 116 ms
23,816 KB
testcase_57 AC 115 ms
23,512 KB
testcase_58 AC 115 ms
23,924 KB
testcase_59 AC 115 ms
24,136 KB
testcase_60 AC 115 ms
23,456 KB
testcase_61 AC 114 ms
23,292 KB
testcase_62 AC 147 ms
23,212 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <string.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <ciso646>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP_OVERLOAD(arg1, arg2, arg3, arg4, NAME, ...) NAME
#define REP3(i, l, r, s)                                               \
    for (int i = int(l), rep3_r = int(r), rep3_s = int(s); i < rep3_r; \
         i += rep3_s)
#define REP2(i, l, r) REP3(i, l, r, 1)
#define REP1(i, n) REP2(i, 0, n)
#define rep(...) REP_OVERLOAD(__VA_ARGS__, REP3, REP2, REP1, )(__VA_ARGS__)
#define repin(i, l, r) for (int i = int(l), repin_r = int(r); i <= repin_r; ++i)

#define RREP_OVERLOAD(arg1, arg2, arg3, arg4, NAME, ...) NAME
#define RREP3(i, l, r, s)                                                      \
    for (int i = int(r) - 1, rrep3_l = int(l), rrep3_s = int(s); i >= rrep3_l; \
         i -= rrep3_s)
#define RREP2(i, l, r) RREP3(i, l, r, 1)
#define RREP1(i, n) RREP2(i, 0, n)
#define rrep(...) RREP_OVERLOAD(__VA_ARGS__, RREP3, RREP2, RREP1, )(__VA_ARGS__)
#define rrepin(i, l, r) \
    for (int i = int(r), rrepin_l = int(l); i >= rrepin_l; --i)

#define fi first
#define se second

#include <atcoder/string>

#include <algorithm>
#include <cassert>
#include <vector>

namespace rklib {

template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
bool chmin_non_negative(T &a, const T &b) {
    if (a < 0 || a > b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
T div_floor(T num, T den) {
    if (den < 0) num = -num, den = -den;
    return num >= 0 ? num / den : (num + 1) / den - 1;
}

template <class T>
T div_ceil(T num, T den) {
    if (den < 0) num = -num, den = -den;
    return num <= 0 ? num / den : (num - 1) / den + 1;
}

}  // namespace rklib


using namespace std;
using namespace rklib;

using lint = long long;
using pii = pair<int, int>;
using pll = pair<lint, lint>;

template <typename T, T inf>
class LiChaoTree {
   public:
    LiChaoTree() = default;
    explicit LiChaoTree(const std::vector<T>& x) : xs(x) {
        std::sort(xs.begin(), xs.end());
        xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
        n = (int)xs.size();
        sz = 1;
        while (sz < n) sz <<= 1;
        while ((int)xs.size() < sz) xs.emplace_back(xs.back() + 1);
        node.resize(sz * 2, Line(T(0), inf));
    }
    // 直線 ax + b を追加
    void add_line(T a, T b) { update(a, b, 0, sz, 1); }
    // 線分 ax + b (x_l <= x < x_r) を追加
    void add_segment(T a, T b, T x_l, T x_r) {
        int l = std::lower_bound(xs.begin(), xs.end(), x_l) - xs.begin();
        int r = std::lower_bound(xs.begin(), xs.end(), x_r) - xs.begin();
        l += sz;
        r += sz;
        int width = 1, seg_idx_left = sz;
        while (l < r) {
            if (l & 1) {
                int L = (l - seg_idx_left) * width;
                int R = L + width;
                update(a, b, L, R, l);
                l++;
            }
            if (r & 1) {
                r--;
                int L = (r - seg_idx_left) * width;
                int R = L + width;
                update(a, b, L, R, r);
            }
            l >>= 1;
            r >>= 1;
            width <<= 1;
            seg_idx_left >>= 1;
        }
    }
    // min_{i} (a_i * x + b) を求める
    T get_min(T x) {
        int pos = std::lower_bound(xs.begin(), xs.end(), x) - xs.begin();
        assert(0 <= pos and pos < sz);
        pos += sz;
        T ret = node[pos].eval(x);
        while (pos > 1) {
            pos >>= 1;
            ret = std::min(ret, node[pos].eval(x));
        }
        return ret;
    }

   private:
    struct Line {
        T a, b;
        Line(T a, T b) : a(a), b(b) {}
        inline T eval(T x) const { return (a * x + b); }
    };
    std::vector<T> xs;
    std::vector<Line> node;
    int n, sz;

    void update(T a, T b, int l, int r, int pos) {
        Line new_line(a, b);
        while (1) {
            bool is_over_l = (new_line.eval(xs[l]) >= node[pos].eval(xs[l]));
            bool is_over_r =
                (new_line.eval(xs[r - 1]) >= node[pos].eval(xs[r - 1]));
            if (is_over_l == is_over_r) {
                if (!is_over_l) node[pos] = new_line;
                break;
            }
            int mid = (l + r) >> 1;
            bool is_over_mid =
                (new_line.eval(xs[mid]) >= node[pos].eval(xs[mid]));
            if (!is_over_l and is_over_r) {
                if (is_over_mid) {
                    r = mid;
                    pos = (pos << 1);
                } else {
                    std::swap(new_line, node[pos]);
                    l = mid;
                    pos = (pos << 1) | 1;
                }
            } else {
                if (is_over_mid) {
                    l = mid;
                    pos = (pos << 1) | 1;
                } else {
                    std::swap(new_line, node[pos]);
                    r = mid;
                    pos = (pos << 1);
                }
            }
        }
    }
};

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<int> a(n), b(m);
    rep(i, n) scanf("%d", &a[i]);
    rep(i, m) scanf("%d", &b[i]);
    vector<lint> c(m);
    rep(i, m) scanf("%lld", &c[i]);

    vector<int> ab = a;
    ab.push_back(-1);
    for (auto x : b) ab.push_back(x);
    auto z = atcoder::z_algorithm(ab);
    z.erase(z.begin(), z.begin() + n + 1);

    vector<lint> xs(m + 10);
    iota(xs.begin(), xs.end(), 0);
    LiChaoTree<lint, LLONG_MAX> lct(xs);
    lct.add_segment(0, 0, 0, 1);

    rep(x, m) {
        auto val = lct.get_min(x);
        if (val == LLONG_MAX) continue;

        if (z[x] >= 1) {
            lct.add_segment(c[x], val - c[x] * x, x + 1, x + z[x] + 1);
        }
    }

    auto ans = lct.get_min(m);
    printf("%lld\n", ans == LLONG_MAX ? -1 : ans);
}
0