oj.uz

Submission #1038485

# Submission time Handle Problem Language Result Execution time Memory
1038485 2024-07-29T21:00:36 Z Wael Fire (JOI20_ho_t5) C++17
6 / 100
 230 ms 70676 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 160 ms 69160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 174 ms 70676 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 67648 KB Output is correct
2 Correct 205 ms 68116 KB Output is correct
3 Correct 210 ms 70220 KB Output is correct
4 Correct 219 ms 67824 KB Output is correct
5 Correct 207 ms 68172 KB Output is correct
6 Correct 195 ms 68108 KB Output is correct
7 Correct 205 ms 69832 KB Output is correct
8 Correct 214 ms 69304 KB Output is correct
9 Correct 208 ms 68128 KB Output is correct
10 Correct 230 ms 68604 KB Output is correct
11 Correct 226 ms 68256 KB Output is correct
12 Correct 221 ms 68804 KB Output is correct
13 Correct 215 ms 68116 KB Output is correct
14 Correct 216 ms 68424 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -