제출 #1038485

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038485		Wael	Fire (JOI20_ho_t5)	C++17	6 / 100	230 ms	70676 KiB

ho_t5

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

using i64 = long long;

struct Fenwick {
    int n;
    vector<i64> val, inc;
    Fenwick(int n) : n(n) {
        val.assign(n, 0);
        inc.assign(n, 0);
    }

    void update(int i, int w, int v, int t) {
        for (; i < n; i |= (i + 1)) {
            val[i] += t * (w - v);
            inc[i] += (v - w);
        }
    }

    i64 query(int i, int t) {
        i64 res = 0;
        for (; i >= 0; i = (i & (i + 1)) - 1) {
            res += val[i] + inc[i] * t;
        }
        return res;
    }

    i64 get(int l, int r, int t) {
        return query(r, t) - query(l - 1, t);
    }
};

void solve() {    
    int n, q;
    cin >> n >> q;

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

    int const lg = 20;
    vector<i64> pref(n);
    vector<vector<pair<int, int>>> sparse(n, vector<pair<int, int>>(lg));
    for (int i = 0; i < n; ++i) {
        sparse[i][0] = {a[i], i};
        pref[i] = a[i] + (i ? pref[i - 1] : 0);
    }

    for (int j = 1; j < lg; ++j) {
        for (int i = 0; i < n; ++i) {
            int ni = min(n - 1, i + (1 << (j - 1)));
            sparse[i][j] = max(sparse[i][j - 1], sparse[ni][j - 1]);
        }
    }

    vector<int> t(q), l(q), r(q);
    for (int i = 0; i < q; ++i) {
        cin >> t[i] >> l[i] >> r[i];
        --l[i], --r[i];
        t[i] = min(t[i], n - 1);
    }

    vector<vector<int>> queries(n);
    for (int i = 0; i < q; ++i) {
        queries[t[i]].push_back(i);
    }

    vector<int> stk;
    vector<vector<int>> update(n);
    for (int i = n - 1; i >= 0; --i) {
        while (stk.size() && a[i] > a[stk.back()]) {
            update[stk.back() - i - 1].push_back(i);
            stk.pop_back();
        }
        int nxt = (stk.size() ? stk.back() : n);
        update[nxt - i - 1].push_back(i);
        stk.push_back(i);
    }

    vector<i64> ans(q);
    Fenwick bit(n);

    auto query = [&](int l, int r, int t) -> i64 {
        if (l > r) {
            return 0;
        }
        i64 res = 0;
        t = min(t, r);
        int d = __lg(t + 1);
        auto [mx, index] = max(sparse[r - t][d], sparse[r - (1 << d) + 1][d]);
        res = 1LL * mx * (r - index + 1);
        res += bit.get(0, index - 1, t);
        res += (index ? pref[index - 1] : 0);
        return res;
    };

    vector<int> was(n);
    for (int t = 0; t < n; ++t) {
        for (auto i : update[t]) {
            int dif = (i + t + 1 < n && a[i + t + 1] < a[i] ? a[i] - a[i + t + 1] : 0);
            bit.update(i, was[i], dif, t);
            was[i] = dif;
        }

        for (auto i : queries[t]) {
            ans[i] = query(0, r[i], t) - query(0, l[i] - 1, t);
        }
    }

    for (int i = 0; i < q; ++i) {
        cout << ans[i] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

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