Submission #1200720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200720		algoproclub	Fish 3 (JOI24_fish3)	C++20	9 / 100	2094 ms	7484 KiB

Main

// UUID: fb67765f-a467-4096-9418-8a18829792eb
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 300'001;
const ll INF = 1e16;

ll c[MAXN];

void solve() {
    ll n, d; cin >> n >> d;
    for (int i = 1; i <= n; i++) cin >> c[i];
    int q; cin >> q;
    while (q--) {
        int l, r; cin >> l >> r;
        vector<ll> mn(n+2, INF);
        vector<ll> v(n+2);
        ll sm = 0, ans = 0;
        bool ok = true;
        for (int i = l; i <= r; i++) {
            if (c[i] - sm < 0) ok = false;
            ll x = (c[i] - sm) % d;
            sm += x;
            ans += (c[i] - sm) / d;
            v[i] = (c[i] - sm) / d;
        }
        for (int i = r; i >= l; i--) {
            mn[i] = min(mn[i+1], v[i]);
        }
        ll sm2 = 0;
        for (int i = l; i <= r; i++) {
            ll x = mn[i] - sm2;
            ans -= x*(r-i+1);
            sm2 += mn[i] - sm2;
        }
        
        if (ok) cout << ans << "\n";
        else cout << "-1\n";
    }
}

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

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