結果

問題 No.2332 Make a Sequence
ユーザー firiexpfiriexp
提出日時 2023-05-01 13:24:05
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 154 ms / 2,000 ms
コード長 4,166 bytes
コンパイル時間 1,222 ms
コンパイル使用メモリ 117,712 KB
実行使用メモリ 20,788 KB
最終ジャッジ日時 2024-04-30 16:16:48
合計ジャッジ時間 14,976 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 93 ms
19,292 KB
testcase_08 AC 32 ms
5,760 KB
testcase_09 AC 89 ms
13,232 KB
testcase_10 AC 84 ms
18,032 KB
testcase_11 AC 54 ms
11,496 KB
testcase_12 AC 115 ms
20,752 KB
testcase_13 AC 117 ms
20,784 KB
testcase_14 AC 114 ms
20,528 KB
testcase_15 AC 115 ms
20,660 KB
testcase_16 AC 115 ms
20,528 KB
testcase_17 AC 118 ms
20,656 KB
testcase_18 AC 118 ms
20,672 KB
testcase_19 AC 121 ms
20,664 KB
testcase_20 AC 116 ms
20,660 KB
testcase_21 AC 116 ms
20,656 KB
testcase_22 AC 112 ms
20,656 KB
testcase_23 AC 113 ms
20,656 KB
testcase_24 AC 113 ms
20,528 KB
testcase_25 AC 113 ms
20,656 KB
testcase_26 AC 112 ms
20,756 KB
testcase_27 AC 117 ms
20,788 KB
testcase_28 AC 113 ms
20,668 KB
testcase_29 AC 114 ms
20,780 KB
testcase_30 AC 117 ms
20,608 KB
testcase_31 AC 113 ms
20,656 KB
testcase_32 AC 114 ms
20,700 KB
testcase_33 AC 116 ms
20,780 KB
testcase_34 AC 114 ms
20,656 KB
testcase_35 AC 113 ms
20,784 KB
testcase_36 AC 114 ms
20,484 KB
testcase_37 AC 114 ms
20,780 KB
testcase_38 AC 117 ms
20,528 KB
testcase_39 AC 115 ms
20,488 KB
testcase_40 AC 115 ms
20,652 KB
testcase_41 AC 112 ms
20,788 KB
testcase_42 AC 115 ms
20,772 KB
testcase_43 AC 115 ms
20,652 KB
testcase_44 AC 114 ms
20,784 KB
testcase_45 AC 115 ms
20,656 KB
testcase_46 AC 122 ms
20,656 KB
testcase_47 AC 154 ms
20,660 KB
testcase_48 AC 147 ms
20,652 KB
testcase_49 AC 140 ms
20,780 KB
testcase_50 AC 140 ms
20,656 KB
testcase_51 AC 142 ms
20,652 KB
testcase_52 AC 140 ms
20,528 KB
testcase_53 AC 112 ms
20,780 KB
testcase_54 AC 115 ms
20,784 KB
testcase_55 AC 111 ms
20,780 KB
testcase_56 AC 111 ms
20,668 KB
testcase_57 AC 110 ms
20,784 KB
testcase_58 AC 111 ms
20,652 KB
testcase_59 AC 114 ms
20,652 KB
testcase_60 AC 115 ms
20,484 KB
testcase_61 AC 113 ms
20,652 KB
testcase_62 AC 154 ms
20,656 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>
#include <limits>

static const int MOD = 998244353;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

template <typename T, T INF>
class LiChaoTree {
    struct Line {
        T a, b;
        Line(T a, T b) : a(a), b(b) {}
        inline T eval(T x) const { return a * x + b; }
        inline bool over(const Line &other, const T &x) const {
            return eval(x) < other.eval(x);
        }
    };

    void inner_update(T a, T b, int left, int right, int seg_idx){
        Line line(a, b);
        while (true){
            int mid = (left + right) >> 1;
            bool l_over = line.over(seg[seg_idx], xset[left]);
            bool r_over = line.over(seg[seg_idx], xset[right-1]);
            if(l_over == r_over){
                if(l_over) swap(seg[seg_idx], line);
                return;
            }
            bool m_over = line.over(seg[seg_idx], xset[mid]);
            if(m_over) swap(seg[seg_idx], line);
            if(l_over != m_over) seg_idx = seg_idx << 1, right = mid;
            else seg_idx = seg_idx << 1 | 1, left = mid;
        }
    }

    void inner_update(T a, T b, int seg_idx){
        int left, right;
        int bit = 31 - __builtin_clz(seg_idx);
        left = (sz >> bit) * (seg_idx - (1 << bit));
        right = left + (sz >> bit);
        inner_update(a, b, left, right, seg_idx);
    }


    T inner_query(int x, int seg_idx) {
        T ret = seg[seg_idx].eval(x);
        while (seg_idx > 1) {
            seg_idx = seg_idx >> 1;
            ret = min(ret, seg[seg_idx].eval(x));
        }
        return ret;
    }

public:
    vector<T> xset;
    vector<Line> seg;
    int sz;

    LiChaoTree(const vector<T> &xs) : xset(xs) {
        sort(xset.begin(),xset.end());
        xset.erase(unique(xset.begin(),xset.end()),xset.end());
        sz = 1;
        while(sz < xset.size()) sz <<= 1;
        while(xset.size() < sz) xset.emplace_back(xset.back() + 1);
        seg.assign(2 * sz, Line(0, INF));
    }

    void update_line(T a, T b) { inner_update(a, b, 0, sz, 1); }

    void update_segment(T a, T b, T l, T r){
        int l_z = lower_bound(xset.begin(),xset.end(),l) - xset.begin() + sz;
        int r_z = lower_bound(xset.begin(),xset.end(),r) - xset.begin() + sz;
        for (; l_z < r_z; l_z >>= 1, r_z >>= 1) {
            if (l_z & 1) inner_update(a, b, l_z++);
            if (r_z & 1) inner_update(a, b, --r_z);
        }
    }

    T query_idx(int k){
        const T x = xset[k];
        return inner_query(x, k+sz);
    }

    T query(T x) {
        int k = lower_bound(xset.begin(),xset.end(),x) - xset.begin();
        return inner_query(x, k+sz);
    }
};

vector<int> Z_algorithm(const vector<int> &s){
    vector<int> res(s.size());
    for (int i = 1, j = 0; i < s.size(); ++i) {
        if(i + res[i-j] < j + res[j]) res[i] = res[i-j];
        else {
            int k = max(0, j + res[j]-i);
            while(i + k < s.size() && s[k] == s[i+k]) ++k;
            res[i] = k;
            j = i;
        }
    }
    res.front() = s.size();
    return res;
}


int main() {
    int n, m;
    cin >> n >> m;
    vector<int> A(n);
    for (auto &&i : A) scanf("%d", &i);
    vector<int> B(m);
    for (auto &&i : B) scanf("%d", &i);
    vector<int> C(m);
    for (auto &&i : C) scanf("%d", &i);
    vector<ll> idx(m+2);
    iota(idx.begin(),idx.end(), 0);
    LiChaoTree<ll, INF<ll>> seg(idx);

    vector<int> AB(n+m+1);
    for (int i = 0; i < n; ++i) {
        AB[i] = A[i];
    }
    AB[n] = -1;
    for (int i = 0; i < m; ++i) {
        AB[i+n+1] = B[i];
    }
    auto Z = Z_algorithm(AB);
    seg.update_segment(0, 0, 0, 1);
    for (int i = 0; i < m; ++i){
        int len = Z[i+n+1];
        ll val = seg.query(i);
        seg.update_segment(C[i], val-(ll)C[i]*i, i+1, i+len+1);
    }
    ll ans = seg.query_idx(m);
    if(ans == INF<ll>) puts("-1");
    else cout << ans << "\n";
    return 0;
}
0