結果

問題 No.2332 Make a Sequence
ユーザー firiexpfiriexp
提出日時 2023-05-01 13:24:05
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 164 ms / 2,000 ms
コード長 4,166 bytes
コンパイル時間 1,629 ms
コンパイル使用メモリ 115,492 KB
実行使用メモリ 20,800 KB
最終ジャッジ日時 2024-11-20 12:59:20
合計ジャッジ時間 16,994 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 61
権限があれば一括ダウンロードができます

ソースコード

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