Submission #1214098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214098		_callmelucian	Dungeon 3 (JOI21_ho_t5)	C++17	100 / 100	656 ms	75776 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;
const int maxU = 1e8;

ll energy[mn], cost[mn], pre[mn], sq[mn], tq[mn], uq[mn], n, Q;
ll spt[mn][18], type[mn], eaten[mn], spare[mn], ans[mn];

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 setZero (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 save = 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 save;
        }

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

    vector<int> line[mn];

    void process() {
        for (int i = 0; i < Q; i++)
            if (ans[i] != -1 && spare[i]) line[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.setZero(st.top(), 1, 1, n), st.pop();
            tree.update(i, block, 1, 1, n), st.push(i);

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

struct megaBIT {
    vector<ll> cnt, sum, typeSum, typeCost;
    megaBIT (int sz) : cnt(sz + 1), sum(sz + 1), typeSum(sz + 1), typeCost(sz + 1) {}

    int p (int k) { return k & -k; }

    void update (int pos, ll val) {
        for (int k = pos; k < sum.size(); k += p(k))
            cnt[k] += val, sum[k] += val * cost[pos];
    }

    void upType (int pos, ll U) {
        for (int k = pos; k < sum.size(); k += p(k)) {
            cnt[k] -= U, sum[k] -= U * cost[pos];
            typeSum[k]++, typeCost[k] += cost[pos];
        }
    }

    void downType (int pos, ll U) {
        for (int k = pos; k < sum.size(); k += p(k)) {
            cnt[k] += U, sum[k] += U * cost[pos];
            typeSum[k]--, typeCost[k] -= cost[pos];
        }
    }

    ll preLen (int k, ll U) {
        ll ans = 0;
        for (; k; k -= p(k))
            ans += cnt[k] + U * typeSum[k];
        return ans;
    }
    ll queryLen (int l, int r, ll U) { return preLen(r, U) - preLen(l - 1, U); }

    ll preCost (int k, ll U) {
        ll ans = 0;
        for (; k; k -= p(k))
            ans += sum[k] + U * typeCost[k];
        return ans;
    }
    ll queryCost (int l, int r, ll U) { return preCost(r, U) - preCost(l - 1, U); }

    int walk (ll bound, ll U) {
        ll ans = 0, curSum = 0;
        for (int mask = 1 << 17; mask; mask >>= 1) {
            int nxt = ans | mask;
            if (nxt < sum.size()) {
                ll added = cnt[nxt] + U * typeSum[nxt];
                if (curSum + added < bound) ans = nxt, curSum += added;
            }
        }
        return ans;
    }
};

ll 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], pre[i] = pre[i - 1] + energy[i];
    }
    for (int i = 1; i <= n; i++) cin >> cost[i];
    for (int s = 1; (1 << s) <= n; s++) {
        for (int i = 1; i + (1 << s) - 1 <= 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++) {
        cin >> sq[i] >> tq[i] >> uq[i];
        if (query(sq[i], tq[i] - 1) > uq[i]) ans[i] = -1;
    }

    /// initialize sweep line
    megaBIT tree(n);
    priority_queue<tpl, vector<tpl>, greater<tpl>> events; // < time / dtype / index >
    /*
        type -2: collapsed
        type -1: shrinking
        type 0: stable
        type 1: expanding
    */

    cost[0] = INT_MAX;
    for (int i = 1; i <= n; i++) {
        events.emplace(energy[i - 1], 1, i); // initial alive stage
        tree.update(i, energy[i - 1]);
    }
    for (int i = 0; i < Q; i++)
        if (ans[i] != -1) events.emplace(uq[i], 3, i); // querying event

    /// let's sweep line !!
    while (events.size() && get<0>(events.top()) <= maxU) {
        int U, dtype, id; tie(U, dtype, id) = events.top(); events.pop();
        if (dtype == 3) { // querying
            int L = sq[id], R = tq[id] - 1;
            int stopBlock = tree.walk(pre[R], U) + 1;
            if (L <= stopBlock) {
                ans[id] = tree.queryCost(L, stopBlock, U) - (tree.preLen(stopBlock, U) - pre[R]) * cost[stopBlock];
                ans[id] -= max(0LL, pre[L - 1] - tree.preLen(L - 1, U)) * cost[L];
                spare[id] = max(0LL, tree.preLen(L - 1, U) - pre[L - 1]);
            }
            else spare[id] = pre[R] - pre[L - 1];
        }

        if (type[id] == -2) continue;
        if (dtype == 1) {
            int eat = tree.walk(tree.preLen(id, U), U);
            if (cost[eat] > cost[id]) { // start eating
                type[id]++, tree.upType(id, U);
                if (eat) type[eat]--, tree.downType(eat, U), eaten[eat] = id;
                if (type[eat] == -1) {
                    ll nxtEvent = U + tree.queryLen(eat, eat, U);
                    events.emplace(nxtEvent, 0, id), events.emplace(nxtEvent, 2, eat);
                }
            }
        }
        if (dtype == 0) {
            int eat = tree.walk(tree.preLen(id - 1, U), U) + 1;
            if (cost[eat] > cost[id]) { // keep eating
                if (eaten[eat] == id) continue;
                tree.downType(eat, U), type[eat]--, eaten[eat] = id;
                if (type[eat] == -1) {
                    ll nxtEvent = U + tree.queryLen(eat, eat, U);
                    events.emplace(nxtEvent, 0, id), events.emplace(nxtEvent, 2, eat);
                }
            }
            else {
                type[id]--, tree.downType(id, U);
                if (type[id] == -1) {
                    ll nxtEvent = U + tree.queryLen(id, id, U);
                    events.emplace(nxtEvent, 0, eaten[id]), events.emplace(nxtEvent, 2, id);
                }
            }
        }
        if (dtype == 2) {
            if (type[id] != -1 || tree.queryLen(id, id, U)) continue;
            tree.upType(id, U), type[id]--;
        }

//        cout << "event " << U << ": ";
//        for (int i = 1; i <= n; i++) cout << tree.queryLen(i, i, U) << " ";
//        cout << "\n";
//        cout << "          ";
//        for (int i = 1; i <= n; i++) cout << type[i] << " ";
//        cout << "\n";
    }

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


    return 0;
}

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