Submission #597647

#	Time	Username	Problem	Language	Result	Execution time	Memory
597647		piOOE	Dungeon 3 (JOI21_ho_t5)	C++17	0 / 100	388 ms	165644 KiB

Main

#include <bits/stdc++.h>

using namespace std;

//thanks, ormlis!
struct SmartFenwick {
    vector<long long> k, b; //kx + b
    int n;

    SmartFenwick(int x) {
        n = x;
        k.assign(x, 0), b.assign(x, 0);
    }

    SmartFenwick() = default;

    void init(int x) {
        n = x;
        k.assign(x, 0);
        b.assign(x, 0);
    }

    void add1(int i, long long mul, long long ad) {
        while (i < n) {
            k[i] += mul;
            b[i] += ad;
            i |= (i + 1);
        }
    }

    //[l, r)
    void modify(int l, int r, long long v) {
        add1(l, v, -v * (l - 1));
        add1((r - 1), -v, v * (r - 1));
    }

    void modify(int i, long long v) {
        add1(i, 0, v);
    }

    long long get(int i) {
        int start = i;
        long long mul = 0, add = 0;
        while (i >= 0) {
            mul += k[i];
            add += b[i];
            i = ((i + 1) & i) - 1;
        }
        return mul * start + add;
    }

    //[l, r)
    long long get(int l, int r) {
        return get(r - 1) - get(l - 1);
    }

};

template<typename T, class F = function<T(const T &, const T &)>>
class SparseTable {
public:
    int n;
    vector<vector<T>> st;
    F func;

    SparseTable(const vector<T> &a, const F &f) : func(f) {
        n = static_cast<int>(a.size());
        int max_log = 32 - __builtin_clz(n);
        st.resize(max_log);
        st[0] = a;
        for (int j = 1; j < max_log; ++j) {
            st[j].resize(n - (1 << j) + 1);
            for (int i = 0; i <= n - (1 << j); ++i) {
                st[j][i] = func(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    SparseTable() = default;

    T get(int L, int R) const {
        assert(0 <= L && L < R && R <= n);
        int lg = __lg(R - L);
        return func(st[lg][L], st[lg][R - (1 << lg)]);
    }
};

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;

    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }

    vector<ll> pref(n + 1);
    partial_sum(a.begin(), a.end(), pref.begin() + 1); //prefix sums

    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    SparseTable<int> mn(ord, [&b](int i, int j) { return b[i] < b[j] ? i : j; }),
            mx(a, [](int i, int j) { return max(i, j); });

    vector<ll> ans(m);

    vector<vector<array<ll, 3>>> updates(n), queries(n);
    for (int i = 0; i < m; ++i) {
        int s, t, u;
        cin >> s >> t >> u;
        --s, --t;
        if (mx.get(s, t) <= u) {
            int _t = lower_bound(pref.begin() + s, pref.begin() + t, pref[t] - u) - pref.begin();
            _t = mn.get(_t, t);
            queries[s].push_back({i, 1, u});
            queries[_t].push_back({i, -1, u});
            ans[i] = (pref[t] - pref[_t]) * (ll) b[_t];
        } else {
            ans[i] = -1;
        }
    }

    vector<int> R(n, n), L(n, -1), stk;
    for (int i = 0; i < n; ++i) {
        while (!stk.empty() && b[stk.back()] > b[i]) {
            R[stk.back()] = i;
            stk.pop_back();
        }
        L[i] = stk.empty() ? -1 : stk.back();
        stk.push_back(i);
    }

    vector<ll> yy;
    for (int i = n - 1; i > -1; --i) {
        updates[i].push_back({0, pref[R[i]] - pref[i], b[i]});
        if (L[i] > -1) {
            updates[L[i]].push_back({pref[i] - pref[L[i]], pref[R[i]] - pref[L[i]], -b[i]});
        }

        for (auto [j, t, u] : queries[i]) {
            yy.push_back(u);
        }

        for (auto [l, r, val] : updates[i]) {
            yy.push_back(l);
            yy.push_back(r);
        }
    }

    sort(yy.begin(), yy.end());
    yy.resize(unique(yy.begin(), yy.end()) - yy.begin());

    auto get = [&yy](ll x) {
        return lower_bound(yy.begin(), yy.end(), x) - yy.begin();
    };

    SmartFenwick fn(yy.size());

    for (int i = n - 1; i > -1; --i) {
        for (auto [l, r, v] : updates[i]) {
            fn.modify(get(l), get(r), v);
        }

        for (auto [j, t, u] : queries[i]) {
            ans[j] += t * fn.get(u - 1);
        }
    }

    for (int i = 0; i < m; ++i) {
        cout << ans[i] << '\n';
    }
    return 0;
}

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