結果

問題 No.2332 Make a Sequence
ユーザー firiexpfiriexp
提出日時 2023-05-01 13:40:26
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 166 ms / 2,000 ms
コード長 4,146 bytes
コンパイル時間 1,370 ms
コンパイル使用メモリ 115,524 KB
実行使用メモリ 20,664 KB
最終ジャッジ日時 2024-11-20 13:11:38
合計ジャッジ時間 13,058 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 110 ms
19,228 KB
testcase_08 AC 30 ms
5,504 KB
testcase_09 AC 85 ms
13,232 KB
testcase_10 AC 95 ms
17,852 KB
testcase_11 AC 63 ms
11,516 KB
testcase_12 AC 132 ms
20,660 KB
testcase_13 AC 132 ms
20,532 KB
testcase_14 AC 131 ms
20,528 KB
testcase_15 AC 132 ms
20,528 KB
testcase_16 AC 132 ms
20,624 KB
testcase_17 AC 130 ms
20,656 KB
testcase_18 AC 132 ms
20,532 KB
testcase_19 AC 132 ms
20,636 KB
testcase_20 AC 132 ms
20,636 KB
testcase_21 AC 131 ms
20,656 KB
testcase_22 AC 132 ms
20,528 KB
testcase_23 AC 133 ms
20,664 KB
testcase_24 AC 133 ms
20,660 KB
testcase_25 AC 132 ms
20,652 KB
testcase_26 AC 131 ms
20,532 KB
testcase_27 AC 133 ms
20,652 KB
testcase_28 AC 132 ms
20,528 KB
testcase_29 AC 133 ms
20,660 KB
testcase_30 AC 133 ms
20,528 KB
testcase_31 AC 133 ms
20,656 KB
testcase_32 AC 134 ms
20,636 KB
testcase_33 AC 134 ms
20,528 KB
testcase_34 AC 133 ms
20,532 KB
testcase_35 AC 134 ms
20,532 KB
testcase_36 AC 134 ms
20,656 KB
testcase_37 AC 133 ms
20,656 KB
testcase_38 AC 133 ms
20,528 KB
testcase_39 AC 134 ms
20,528 KB
testcase_40 AC 133 ms
20,528 KB
testcase_41 AC 134 ms
20,528 KB
testcase_42 AC 137 ms
20,656 KB
testcase_43 AC 137 ms
20,528 KB
testcase_44 AC 136 ms
20,528 KB
testcase_45 AC 138 ms
20,528 KB
testcase_46 AC 138 ms
20,656 KB
testcase_47 AC 166 ms
20,528 KB
testcase_48 AC 166 ms
20,620 KB
testcase_49 AC 166 ms
20,652 KB
testcase_50 AC 166 ms
20,532 KB
testcase_51 AC 165 ms
20,528 KB
testcase_52 AC 133 ms
20,528 KB
testcase_53 AC 132 ms
20,528 KB
testcase_54 AC 133 ms
20,532 KB
testcase_55 AC 133 ms
20,532 KB
testcase_56 AC 133 ms
20,528 KB
testcase_57 AC 133 ms
20,580 KB
testcase_58 AC 133 ms
20,656 KB
testcase_59 AC 132 ms
20,596 KB
testcase_60 AC 133 ms
20,660 KB
testcase_61 AC 132 ms
20,656 KB
testcase_62 AC 152 ms
20,528 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];
    }
    for (int i = 0; i < m; ++i) {
        AB[i+n] = 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];
        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