Submission #593065

#	Time	Username	Problem	Language	Result	Execution time	Memory
593065		piOOE	Fire (JOI20_ho_t5)	C++17	100 / 100	304 ms	30296 KiB

ho_t5

#include <bits/stdc++.h>

using namespace std;

template<typename T>
struct Fenwick {
    vector<T> t;
    int n;

    Fenwick(int x) {
        n = x;
        t.assign(x + 1, 0);
    }

    Fenwick() = default;

    T get(int i) {
        T ans = 0;
        for (; i > 0; i -= i & -i)
            ans += t[i];
        return ans;
    }

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

    void modify(int i, T v) {
        assert(i > 0);
        for (; i <= n; i += i & -i)
            t[i] += v;
    }

};

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> s(n + 1);
    vector<ll> ans(q);
    vector<array<int, 3>> queries[n + 1];
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
    }
    for (int i = 0; i < q; ++i) {
        int t, l, r;
        cin >> t >> l >> r;
        queries[l - 1].push_back({t, -1, i});
        queries[r].push_back({t, 1, i});
    }
    Fenwick<ll> add_l(n), add_q(n), sub_l(n), sub_q(n);
    vector<int> stk;
    ll pref = 0;
    for (int i = 1; i <= n; ++i) {
        auto upd = [&](int len, ll k) {
            add_l.modify(i - len, k);
            add_q.modify(i - len, k * (n - i + len));
            if (len > 1) {
                sub_l.modify(len - 1, k);
                sub_q.modify(len - 1, (len - 1) * k);
            }
        };
        while (!stk.empty() && s[stk.back()] <= s[i]) {
            int b = stk.back();
            stk.pop_back();
            if (!stk.empty()) {
                upd(i - stk.back(), s[b] - s[stk.back()]);
            }
        }
        if (!stk.empty()) {
            upd(i - stk.back(), s[stk.back()] - s[i]);
        }
        stk.push_back(i);
        pref += s[i];
        for (auto [len, k, idx]: queries[i]) {
            ll sum = pref;
            sum += add_q.get(i - len + 1, i + 1) - (n - i) * (add_l.get(i - len + 1, i + 1));
            sum += len * (add_l.get(i - len) - (sub_l.get(n) - sub_l.get(len)));
            sum -= sub_q.get(len);
            ans[idx] += sum * k;
        }
    }
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80