結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 93 ms
19,300 KB
testcase_08 AC 24 ms
6,940 KB
testcase_09 AC 73 ms
13,288 KB
testcase_10 AC 79 ms
18,008 KB
testcase_11 AC 53 ms
11,508 KB
testcase_12 AC 111 ms
20,604 KB
testcase_13 AC 117 ms
20,676 KB
testcase_14 AC 115 ms
20,592 KB
testcase_15 AC 111 ms
20,608 KB
testcase_16 AC 113 ms
21,504 KB
testcase_17 AC 113 ms
20,716 KB
testcase_18 AC 114 ms
20,716 KB
testcase_19 AC 113 ms
21,644 KB
testcase_20 AC 111 ms
20,756 KB
testcase_21 AC 111 ms
20,600 KB
testcase_22 AC 117 ms
20,700 KB
testcase_23 AC 120 ms
20,588 KB
testcase_24 AC 122 ms
20,756 KB
testcase_25 AC 119 ms
20,824 KB
testcase_26 AC 125 ms
21,680 KB
testcase_27 AC 118 ms
20,704 KB
testcase_28 AC 121 ms
20,608 KB
testcase_29 AC 122 ms
21,040 KB
testcase_30 AC 121 ms
20,680 KB
testcase_31 AC 115 ms
20,660 KB
testcase_32 AC 122 ms
20,720 KB
testcase_33 AC 122 ms
20,608 KB
testcase_34 AC 122 ms
21,272 KB
testcase_35 AC 114 ms
20,668 KB
testcase_36 AC 126 ms
20,896 KB
testcase_37 AC 127 ms
20,484 KB
testcase_38 AC 122 ms
20,592 KB
testcase_39 AC 114 ms
21,084 KB
testcase_40 AC 116 ms
20,944 KB
testcase_41 AC 119 ms
20,784 KB
testcase_42 AC 121 ms
21,592 KB
testcase_43 AC 121 ms
20,700 KB
testcase_44 AC 115 ms
20,600 KB
testcase_45 AC 121 ms
20,832 KB
testcase_46 AC 134 ms
20,904 KB
testcase_47 AC 150 ms
20,892 KB
testcase_48 AC 145 ms
20,752 KB
testcase_49 AC 144 ms
20,668 KB
testcase_50 AC 144 ms
20,708 KB
testcase_51 AC 143 ms
20,704 KB
testcase_52 AC 113 ms
20,816 KB
testcase_53 AC 114 ms
21,108 KB
testcase_54 AC 114 ms
20,796 KB
testcase_55 AC 114 ms
21,028 KB
testcase_56 AC 116 ms
20,708 KB
testcase_57 AC 111 ms
20,676 KB
testcase_58 AC 114 ms
21,168 KB
testcase_59 AC 115 ms
20,576 KB
testcase_60 AC 112 ms
20,752 KB
testcase_61 AC 113 ms
20,752 KB
testcase_62 AC 129 ms
20,816 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