제출 #1213745

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213745		_callmelucian	Dungeon 3 (JOI21_ho_t5)	C++17	11 / 100	4091 ms	30992 KiB

Main

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

using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 2e5 + 5;
ll energy[mn], cost[mn], sq[mn], tq[mn], uq[mn], ans[mn], spare[mn];
int n, Q;

namespace processSpare {
    struct IT {
        vector<ll> cnt, sum;
        IT (int sz) : cnt(sz << 2), sum(sz << 2) {}

        void update (int pos, ll val, int k, int l, int r) {
            while (l < r) {
                int mid = (l + r) >> 1;
                if (pos <= mid) k <<= 1, r = mid;
                else k <<= 1, k |= 1, l = mid + 1;
            }
            cnt[k] += val, sum[k] += val * cost[pos];
            for (k >>= 1; k >= 1; k >>= 1) {
                cnt[k] = cnt[k << 1] + cnt[k << 1 | 1];
                sum[k] = sum[k << 1] + sum[k << 1 | 1];
            }
        }

        ll del (int pos, int k, int l, int r) {
            while (l < r) {
                int mid = (l + r) >> 1;
                if (pos <= mid) k <<= 1, r = mid;
                else k <<= 1, k |= 1, l = mid + 1;
            }
            ll ans = cnt[k];
            cnt[k] = sum[k] = 0;
            for (k >>= 1; k >= 1; k >>= 1) {
                cnt[k] = cnt[k << 1] + cnt[k << 1 | 1];
                sum[k] = sum[k << 1] + sum[k << 1 | 1];
            }
            return ans;
        }

        ll walk (ll need, int k, int l, int r) {
            ll ans = 0;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (cnt[k << 1] >= need) k <<= 1, r = mid;
                else {
                    ans += sum[k << 1], need -= cnt[k << 1];
                    k <<= 1, k |= 1, l = mid + 1;
                }
            }
            return ans += need * cost[l];
        }
    };

    vector<int> pr[mn];

    void process() {
        for (int i = 0; i < Q; i++)
            if (ans[i] != -1) pr[sq[i]].push_back(i);

        IT tree(n); stack<int> st;
        for (int i = n; i >= 1; i--) {
            ll block = energy[i];
            while (st.size() && cost[i] <= cost[st.top()])
                block += tree.del(st.top(), 1, 1, n), st.pop();
            tree.update(i, block, 1, 1, n), st.push(i);

            for (int u : pr[i])
                ans[u] += tree.walk(spare[u], 1, 1, n);
        }
    }
};

namespace brute {
    ll solve (int l, int r, int U) {
        map<ll,ll> mp;
        vector<int> erased;
        ll sumCands = 0, ans = 0;

        for (int i = l; i <= r; i++) {
            if (energy[i] > U) return -1;
            mp[cost[i]] += U, sumCands += U;
            for (auto it = mp.rbegin(); it != mp.rend() && sumCands > U; it++) {
                ll subtract = min(it->second, sumCands - U);
                sumCands -= subtract, it->second -= subtract;
                if (!it->second) erased.push_back(it->first);
            }
            for (int u : erased) mp.erase(u);
            erased.clear();

            ll used = energy[i];
            for (auto it = mp.begin(); it != mp.end() && used > 0; it++) {
                ll subtract = min(it->second, used);
                used -= subtract, it->second -= subtract, sumCands -= subtract;
                ans += 1LL * it->first * subtract;
                if (!it->second) erased.push_back(it->first);
            }
            for (int u : erased) mp.erase(u);
            erased.clear();
        }
        return ans;
    }

    void solve() {
        for (int i = 0; i < Q; i++) {
            if (ans[i] == -1) cout << -1 << "\n";
            else cout << solve(sq[i], tq[i] - 1, uq[i]) << "\n";
        }
    }

    bool check() { return 1; }
}

namespace sameU {
    ll pre[mn], preLen[mn], preCost[mn];
    ll block[mn], U;

    void solve() {
        /// compute block sizes
        block[1] = U;
        stack<int> st; st.push(1); // maintain non-empty blocks
        for (int i = 2; i <= n; i++) {
            block[i] = energy[i - 1];
            ll spare = U - energy[i - 1];
            while (spare && st.size() && cost[st.top()] > cost[i]) {
                ll take = min(spare, block[st.top()]);
                spare -= take, block[st.top()] -= take, block[i] += take;
                if (!block[st.top()]) st.pop();
            }
            st.push(i);
        }
//        for (int i = 1; i <= n; i++) cout << block[i] << " ";
//        cout << "\n";

        /// prefix sums
        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + energy[i];
            preLen[i] = preLen[i - 1] + block[i];
            preCost[i] = preCost[i - 1] + block[i] * cost[i];
        }

        /// process queries
        for (int i = 0; i < Q; i++) {
            if (ans[i] == -1) continue;
            ll L = sq[i], R = tq[i] - 1;
            int stopBlock = lower_bound(preLen, preLen + 1 + n, pre[R]) - preLen;
            ans[i] = preCost[stopBlock] - preCost[L - 1] - (preLen[stopBlock] - pre[R]) * cost[stopBlock];
            spare[i] = preLen[L - 1] - pre[L - 1];

//            cout << "query " << i << " " << ans[i] << " " << spare[i] << "\n";
        }

        /// process spare
        processSpare::process();
        for (int i = 0; i < Q; i++) cout << ans[i] << "\n";
    }

    bool check() {
        U = uq[0];
        for (int i = 1; i < Q; i++)
            if (uq[i] != U) return 0;
        return 1;
    }
};

int spt[mn][21];
int query (int l, int r) {
    int p = 31 - __builtin_clz(r - l + 1);
    return max(spt[l][p], spt[r - (1 << p) + 1][p]);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    /// input
    cin >> n >> Q;
    for (int i = 1; i <= n; i++) {
        cin >> energy[i];
        spt[i][0] = energy[i];
    }
    for (int i = 1; i <= n; i++) cin >> cost[i];
    for (int i = 0; i < Q; i++)
        cin >> sq[i] >> tq[i] >> uq[i];

    /// process invalid queries
    for (int s = 1; (1 << s) <= n; s++) {
        for (int i = 1; i <= n; i++) {
            int p = s - 1;
            spt[i][s] = max(spt[i][p], spt[i + (1 << p)][p]);
        }
    }
    for (int i = 0; i < Q; i++)
        if (query(sq[i], tq[i] - 1) > uq[i]) ans[i] = -1;

    if (sameU::check()) return sameU::solve(), 0;
    if (brute::check()) return brute::solve(), 0;

    return 0;
}

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