Submission #390814

#	Time	Username	Problem	Language	Result	Execution time	Memory
390814		timmyfeng	Fire (JOI20_ho_t5)	C++17	100 / 100	443 ms	51072 KiB

ho_t5

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

const int N = 200001;

struct fenwick {
    vector<long long> tree;
    int n;

    fenwick(int n) : tree(n + 1), n(n) {}

    void update(int a, long long x) {
        for ( ; a <= n; a += a & -a) {
            tree[a] += x;
        }
    }

    long long query(int a) {
        long long sum = 0;
        for ( ; a > 0; a -= a & -a) {
            sum += tree[a];
        }
        return sum;
    }
};

vector<array<long long, 3>> queries[N];
vector<array<long long, 2>> updates[N];
long long s[N], ans[N];

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

    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
    }

    for (int i = 1; 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});
    }

    vector<int> stack;
    for (int i = 1; i <= n; ++i) {
        while (!stack.empty() && s[stack.back()] <= s[i]) {
            int j = stack.back();
            stack.pop_back();
            if (!stack.empty()) {
                int k = stack.back();
                updates[i].push_back({i - k, s[j] - s[k]});
            }
        }

        if (!stack.empty()) {
            int j = stack.back();
            updates[i].push_back({i - j, s[j] - s[i]});
        }

        stack.push_back(i);
    }

    long long prefix = 0;
    fenwick add_q(n), add_l(n), sub_q(n), sub_l(n);
    for (int i = 1; i <= n; ++i) {
        for (auto [j, k] : updates[i]) {
            add_l.update(i - j, k);
            add_q.update(i - j, (n - i + j) * k);
            if (j > 1) {
                sub_l.update(j - 1, k);
                sub_q.update(j - 1, (j - 1) * k);   
            }
        }

        prefix += s[i];

        for (auto [j, k, l] : queries[i]) {
            long long sum = prefix;
            sum += add_q.query(i) - add_q.query(i - j);
            sum -= (n - i) * (add_l.query(i) - add_l.query(i - j));
            sum += j * add_l.query(i - j);
            sum -= sub_q.query(j);
            sum -= j * (sub_l.query(n) - sub_l.query(j));
            ans[l] += k * sum;
        }
    }

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

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