Submission #597668

#	Time	Username	Problem	Language	Result	Execution time	Memory
597668		piOOE	Dungeon 3 (JOI21_ho_t5)	C++17	100 / 100	1034 ms	129128 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct segtree {
    segtree *left, *right;
    long long sum, lazy, count;

    segtree(int l, int r, vector<long long>& a) {
        lazy = 0;
        if (l + 1 == r) {
            count = a[l + 1] - a[l];
            sum = 0;
        } else {
            int m = (l + r) / 2;
            left = new segtree(l, m, a);
            right = new segtree(m, r, a);
            pull();
        }
    }

    void apply(long long x) {
        sum += count * x, lazy += x;
    }

    void pull() {
        sum = left->sum + right->sum;
        count = left->count + right->count;
    }

    void push() {
        if (lazy != 0) {
            left->apply(lazy);
            right->apply(lazy);
            lazy = 0;
        }
    }

    void modify(int a, int b, long long x, int l, int r) {
        if (a == b || b <= l || r <= a) {
            return;
        } else if (a <= l && r <= b) {
            apply(x);
        } else {
            push();
            int m = (l + r) / 2;
            left->modify(a, b, x, l, m);
            right->modify(a, b, x, m, r);
            pull();
        }
    }

    long long get(int a, int b, int l, int r) {
        if (a == b || b <= l || r <= a) {
            return 0;
        } else if (a <= l && r <= b) {
            return sum;
        } else {
            push();
            int m = (l + r) / 2;
            return left->get(a, b, l, m) + right->get(a, b, m, r);
        }
    }
};

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);
    for (int i = 1; i <= n; ++i) {
        pref[i] = pref[i - 1] + a[i - 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) -> int {
        assert(binary_search(yy.begin(), yy.end(), x));
        return lower_bound(yy.begin(), yy.end(), x) - yy.begin();
    };

    segtree fn(0, yy.size(), yy);

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

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

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

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