Submission #1000580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000580		PurpleCrayon	Fish 3 (JOI24_fish3)	C++17	100 / 100	456 ms	118456 KiB

Main

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

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 3e5+10, MOD = 1e9+7;
const ll INF = 1e18+10;
const int L = 19;

pair<int, ll> anc[N][L];

ll ceil_div(ll x, ll y) {
    return (x + y - 1) / y;
}

void solve() {
    int n; ll k; cin >> n >> k;
    vector<ll> a(n); for (auto& x : a) cin >> x;
    vector<ll> diff(n-1);
    for (int i = 0; i < n-1; i++) {
        if (a[i] <= a[i+1])
            diff[i] = max(0LL, (a[i+1] - a[i]) / k);
        else
            diff[i] = -ceil_div(a[i] - a[i+1], k);
    }

    vector<ll> ps_diff = diff;
    for (int i = 1; i < n-1; i++) {
        ps_diff[i] += ps_diff[i-1];
    }

    vector<int> prv(n-1, -2); // previous thing less than it

    vector<int> stk;
    for (int i = 0; i < n-1; i++) {
        while (sz(stk) && ps_diff[stk.back()] >= ps_diff[i]) stk.pop_back();
        if (sz(stk)) prv[i] = stk.back();
        else prv[i] = ps_diff[i] > 0 ? -1 : -2;
        stk.push_back(i);
    }

    vector<ll> suf1 = diff; suf1.push_back(0);
    for (int i = sz(diff)-1; i >= 0; i--) {
        suf1[i] += suf1[i+1];
    }

    vector<ll> suf2 = suf1;
    for (int i = sz(diff)-1; i >= 0; i--) {
        suf2[i] += suf2[i+1];
    }

    auto qry = [&](int l, int r) {
        if (l > r) return 0LL;
        return -(suf2[l] - suf2[r+1] - suf1[r+1] * (r - l + 1));
    };

    vector<ll> store(n-1);
    for (int i = 0; i < n-1; i++) {
        store[i] = qry(prv[i] + 2, i);
    }

    for (int i = 0; i < n-1; i++) {
        anc[i][0] = {prv[i], store[i]};
    }

    for (int k = 1; k < L; k++) {
        for (int i = 0; i < n; i++) {
            int m = anc[i][k-1].first;
            if (m >= 0) {
                anc[i][k] = {anc[m][k-1].first, anc[i][k-1].second + anc[m][k-1].second};
            } else {
                anc[i][k] = {-2, -2};
            }
        }
    }

    int q; cin >> q;
    while (q--) {
        int l, r; cin >> l >> r, --l, --r;
        if (l == r) {
            ll ans = 0;
            ll p = 0;
            for (int i = r-1; i >= l; i--) {
                if (p >= diff[i]) {
                    p -= diff[i];
                } else {
                    p = 0;
                }

                ans += p;
            }

            if (a[l] - k * p >= 0)
                cout << ans << '\n';
            else
                cout << -1 << '\n';

            continue;
        }

        ll ans = 0;
        int c = r-1;
        for (int i = L-1; i >= 0; i--) {
            while (c >= 0 && anc[c][i].first + 1 >= l) {
                ans += anc[c][i].second;
                c = anc[c][i].first;
            }
        }

        /*
        while (c >= 0 && prv[c] + 1 >= l) { // slow
            ans += store[c]; 
            c = prv[c];
        }
        */

        ll p = 0;
        if (l <= c) {
            p -= (suf1[l] - suf1[c+1]);
        }
        ans += qry(l, c);

        if (a[l] - k * p >= 0)
            cout << ans << '\n';
        else
            cout << -1 << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

• Subtask 1: 9 / 9
• Subtask 2: 7 / 7
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36