제출 #1297100

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1297100		MisterReaper	Peru (RMI20_peru)	C++20	18 / 100	1096 ms	40380 KiB

peru

#include "peru.h"
#include "bits/stdc++.h"

namespace {
    #ifdef DEBUG 
        #include "/home/ahmetalp/Desktop/Workplace/debug.h"
    #else
        #define debug(...) void(23)
    #endif

    using i64 = long long;

    constexpr i64 inf = i64(1E18);
    constexpr int md = int(1E9) + 7;

    #define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l + 1) << 1)
    struct segtree {
        struct node {
            i64 ans = inf;
            i64 lz = 0;
            void modify(i64 x) {
                ans += x;
                lz += x;
            }
        };
        node unite(const node lhs, const node rhs) {
            node res;
            res.ans = std::min(lhs.ans, rhs.ans);
            return res;
        }
        int n;
        std::vector<node> tree;
        segtree(int n_) : n(n_), tree(n << 1) {}
        void push(int v, int l, int r) {
            def;
            tree[lv].modify(tree[v].lz);
            tree[rv].modify(tree[v].lz);
            tree[v].lz = 0;
        }
        void set(int v, int l, int r, int p, i64 x) {
            if (l == r) {
                tree[v].ans = x;
                return;
            }
            def;
            push(v, l, r);
            if (p <= mid) {
                set(lv, l, mid, p, x);
            } else {
                set(rv, mid + 1, r, p, x);
            }
            tree[v] = unite(tree[lv], tree[rv]);
        }
        void set(int p, i64 x) {
            set(0, 0, n - 1, p, x);
        }
        void modify(int v, int l, int r, int ql, int qr, int x) {
            if (ql == l && r == qr) {
                tree[v].modify(x);
                return;
            }
            def;
            if (qr <= mid) {
                modify(lv, l, mid, ql, qr, x);
            } else if (mid + 1 <= ql) {
                modify(rv, mid + 1, r, ql, qr, x);
            } else {
                modify(lv, l, mid, ql, mid, x);
                modify(rv, mid + 1, r, mid + 1, qr, x);
            }
            tree[v] = unite(tree[lv], tree[rv]);
        }
        void modify(int l, int r, int x) {
            modify(0, 0, n - 1, l, r, x);
        }
        i64 get(int v, int l, int r, int ql, int qr) {
            if (ql == l && r == qr) {
                return tree[v].ans;
            }
            def;
            push(v, l, r);
            if (qr <= mid) {
                return get(lv, l, mid, ql, qr);
            } else if (mid + 1 <= ql) {
                return get(rv, mid + 1, r, ql, qr);
            } else {
                return std::min(get(lv, l, mid, ql, mid), get(rv, mid + 1, r, mid + 1, qr));
            }
        }
        i64 get(int l, int r) {
            return get(0, 0, n - 1, l, r);
        }
    };
};

int solve(int N, int K, int* A){
    std::vector<i64> f(N + 1, inf);
    f[0] = 0;
    // segtree seg(N + 1);
    // seg.set(0, 0);
    // std::vector<int> stk {-1};
    std::vector<int> stk;
    std::vector<int> prv(N);
    for (int i = 0; i < N; ++i) {
        while (!stk.empty() && A[stk.back()] <= A[i]) {
            stk.pop_back();
        }
        prv[i] = stk.empty() ? -1 : stk.back();
        stk.emplace_back(i);
    }
    debug(prv);

    std::deque<int> deq;
    for (int i = 1; i <= N; ++i) {
        if (deq.front() == i - K - 1) {
            deq.pop_front();
        }
        while (!deq.empty() && A[deq.back()] <= A[i - 1]) {
            deq.pop_back();
        }
        auto eval = [&](int x) -> i64 {
            return f[std::max(prv[x] + 1, i - K)] + A[x];
        };
        deq.emplace_back(i - 1);
        int n = int(deq.size());
        for (auto j : deq) {
            debug(j, eval(j));
            f[i] = std::min(f[i], eval(j));
        }
        #ifdef LOCAL
            int mx = 0;
            i64 real = inf;
            for (int j = i; j >= std::max(1, i - K + 1); --j) {
                mx = std::max(mx, A[j - 1]);
                real = std::min(real, f[j - 1] + mx);
            }
            mx = 0;
            for (int j = i; j >= std::max(1, i - K + 1); --j) {
                mx = std::max(mx, A[j - 1]);
                real = std::min(real, f[j - 1] + mx);
                if (real == f[j - 1] + mx) {
                    debug(i, j - 1);
                }
            }
            debug(real, f[i]);
            assert(real == f[i]);
        #endif
    }

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        int x = f[i + 1] % md;
        debug(i, x);
        ans = (ans * 23LL + x) % md;
    }

    return ans;
}

• Subtask 1: 18 / 18
• Subtask 2: 0 / 31
• Subtask 3: 0 / 51