제출 #1000578

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1000578		PurpleCrayon	Fish 3 (JOI24_fish3)	C++17	9 / 100	2067 ms	17968 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;

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));

        /*
        ll ans = 0;
        ll p = 0;
        for (int i = r; i >= l; i--) {
            p -= diff[i];
            ans += p;
        }
        return ans;
        */
    };

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

    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;
        while (c >= 0 && prv[c] + 1 >= l) {
            ans += store[c];
            c = prv[c];
        }

        ll p = 0;
        for (int i = c; i >= l; i--) {
            p -= diff[i];
            // ans += p;
        }

        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: 0 / 7
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36