Submission #75559365

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int ll

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

template<class T>
struct RMQ {
    vector<vector<T>> jmp;
    RMQ(const vector<T>& V) : jmp(1, V) {
        for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
            jmp.emplace_back(sz(V) - pw * 2 + 1);
            rep(j,0,sz(jmp[k]))
                jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
        }
    }
    T query(int a, int b) {
        assert(a < b); // or return inf if a == b
        int dep = 31 - __builtin_clz(b - a);
        return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
    }
};

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int>p(n+1);
        vector<int>a(n+1);
        vector<pii>arr(n+1);
        for(int i = 1; i<=n; i++){
            cin >> p[i];
            arr[i] = {p[i],i};
        }
        RMQ rmq(arr);
        for(int i = 1; i<=n; i++){
            cin >> a[i];
        }
        auto merge1 = [&](vi a, int v) -> vi {
            int n = sz(a);
            vi b(n+1,(int)1e18);
            for(int i = 0; i<n; i++){
                b[i] = min(b[i],a[i]);
                b[i+1] = min(b[i+1],a[i] + v);
            }
            return b;
        };
        auto merge = [&](vi a, vi b, int v) -> vi {
            if(a.empty() && b.empty()) return {0,v};
            if(b.empty())return merge1(a,v);
            if(a.empty())return merge1(b,v);
            int n = sz(a); int m = sz(b);
            vi c(n+m,(int)1e18);
            for(int i = 0; i<n; i++){
                for(int j = 0; j<m; j++){
                    bool both = (i > 0 && j > 0);
                    c[i+j +both] = min(c[i+j+both],a[i] + b[j] + v * both);
                    c[i+j+1] = min(c[i+j+1], a[i] + b[j] + v);
                }
            }
            return c;
        };
        auto self = [&](auto &&self, int l, int r) -> vi {
            if(r <= l){
                return {};
            }
            auto [_,m] = rmq.query(l,r);
            vi left = self(self,l,m);
            vi right = self(self,m+1,r);
            return merge(left,right,a[m]);
        };
        vi res = self(self,1,n+1);
        for(int i = 1; i<=n; i++){
            cout << res[i] << " \n"[i==n];
        }
    }
    return 0;
}

Submission Info

Judge Result