// 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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |