Submission #1181267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181267		patgra	Dungeon 3 (JOI21_ho_t5)	C++20	0 / 100	4093 ms	99456 KiB

Main

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

constexpr ll inf = 1e18;
int n, q, maxLog;
vector<ll> dist, cost, answers, mrLeft, mrRight, prefSumDist;
vector<pair<pair<ll, ll>, pair<ll, ll>>> queries;
vector<vector<ll>> stMin, stMax;
vector<pair<pair<ll, ll>, ll>> queriesL;
vector<pair<pair<ll, ll>, pair<ll, ll>>> queriesM;

ll stMinQ(ll l, ll r) {
    int k = 63 - __builtin_clzll(r - l + 1);
    return min(stMin[l][k], stMin[r - (1 << k) + 1][k]);
}

ll stMaxQ(ll l, ll r) {
    int k = 63 - __builtin_clzll(r - l + 1);
    return max(stMax[l][k], stMax[r - (1 << k) + 1][k]);
}

ll calcBuy(ll s, ll t, ll u, ll i) {
    ll buy;
    ll mL, mR;
    if(mrLeft[i] >= s) mL = prefSumDist[i] - prefSumDist[mrLeft[i]];
    else mL = inf;
    if(mrRight[i] <= t) mR = prefSumDist[mrRight[i]] - prefSumDist[i];
    else mR = prefSumDist[t] - prefSumDist[i];
    if(u < min(mL, mR)) buy = u;
    else if(u < max(mL, mR)) buy = min(mL, mR);
    else if(u < mR + mR) buy = mR + mL - u;
    else buy = 0;
    DC << "  at " << i << "  l = " << mL << "  r = " << mR << "  buy = " << buy << eol;
    return buy;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> q;
    dist.resize(n);
    cost.resize(n);
    queries.resize(q);
    answers.resize(q);
    rep(i, 0, n) cin >> dist[i];
    rep(i, 0, n) cin >> cost[i];
    rep(i, 0, q) {
        int s, t, u;
        cin >> s >> t >> u;
        s--; t--;
        queries[i] = {{u, i}, {s, t}};
    }

    maxLog = 32 - __builtin_clz(n + 2);
    stMin.resize(n, vector<ll>(maxLog, inf)), stMax.resize(n, vector<ll>(maxLog, -inf));; 
    rep(i, 0, n) stMin[i][0] = cost[i], stMax[i][0] = dist[i];
    rep(k, 1, maxLog) rep(i, 0, n) stMin[i][k] = min(stMin[i][k - 1], stMin[min(n - 1, i + (1 << (k - 1)))][k - 1]), stMax[i][k] = max(stMax[i][k - 1], stMax[min(n - 1, i + (1 << (k - 1)))][k - 1]);
    mrLeft.resize(n); mrRight.resize(n);
    rep(i, 0, n) {
        int l = -1, r = i, m;
        while(r - 1 > l) {
            m = (l + r) / 2;
            if(stMinQ(m, i - 1) <= cost[i]) l = m;
            else r = m;
        }
        mrLeft[i] = l;
        l = i, r = n;
        while(r - 1 > l) {
            m = (l + r) / 2;
            if(stMinQ(i + 1, m) < cost[i]) r = m;
            else l = m;
        }
        mrRight[i] = r;
        DC << "i " << i << " mrLeft " << mrLeft[i] << " mrRight " << mrRight[i] << eol;
    }

    prefSumDist.resize(n + 1);
    prefSumDist[0] = 0;
    rep(i, 0, n) prefSumDist[i + 1] = prefSumDist[i] + dist[i];
    repIn2(ui, st, queries) {
        auto [u, qi] = ui;
        auto [s, t] = st;
        DC << "query " << qi << "  " << s << ' ' << t << ' ' << u << eol;
        ll ans = 0;
        if(stMaxQ(s, t - 1) > u) { 
            answers[qi] = -1;
            continue;
        }
        ll l = s, r = t + 1, m;
        while(r - l > 1) { 
            m = (l + r) / 2;
            if(prefSumDist[m] - prefSumDist[s] > u) r = m;
            else l = m;
        }
        auto L = l;
        l = s, r = t + 1;
        while(r - l > 1) {
            m = (l + r) / 2;
            if(prefSumDist[t] - prefSumDist[m] > u) l = m;
            else r = m;
        }
        auto R = max(r, L);
        DC << " L " << L << "  R " << R << eol;
   
        l = s, r = L - 1;
        while(r - l > 1) {
            m = (l + r) / 2;
            if(stMinQ(s, L - 1) == stMinQ(s, m)) r = m;
            else l = m;
        }
        auto whereMax = r;
        ans += cost[whereMax] * calcBuy(s, t, u, whereMax);
        DC << " after L ans = " << ans << eol;
        if(whereMax > s) {
            queriesL.pb({{s, whereMax - 1}, qi});
            DC << "  added qL " << s << ' ' << whereMax - 1 << eol;
        }

        if(R < t) {
            auto minn = stMinQ(R, t - 1);
            l = R - 1, r = t - 1;
            while(r - l > 1) {
                m = (l + r) / 2;
                if(stMinQ(R, m) == minn) r = m;
                else l = m;
            }
            auto whereMin = r;
            ans += cost[whereMin] * calcBuy(s, t, u, whereMin);
            R = whereMin;
        }
        DC << " after R ans = " << ans << eol;

        if(L < R) {
            queriesM.pb({{u, qi}, {L, R - 1}});
            DC << "  added qL " << L << ' ' << R - 1 << " at u=" << u << eol;
        }

        answers[qi] = ans;
    }

    ranges::sort(queriesL);
    repIn2(lr, qi, queriesL) {
        auto [l, r] = lr;
        auto curMin = cost[l];
        rep(i, l, r + 1) {
            curMin = min(curMin, cost[i]);
            answers[qi] += curMin * dist[i];
        }
        DC << "After queryL (" << l << ' ' << r << ' ' << qi << ") answer " << answers[qi] << eol;
    }

    ranges::sort(queriesM);
    repIn2(ui, lr, queriesM) {
        auto [u, qi] = ui;
        auto [l, r] = lr;
        auto [s, t] = queries[qi].second;
        rep(i, l, r + 1) {
            auto buy = calcBuy(s, t, u, i);
            answers[qi] += cost[i] * buy;
        }
        DC << "After queryM (" << u << ' ' << qi << ' ' << l << ' ' << r << ") answer " << answers[qi] << eol;
    }

    rep(i, 0, q) cout << answers[i] << '\n';
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 31
• Subtask 4: 0 / 44