#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll d;
const ll inf = 1e18;
signed main() {
int n;
cin >> n >> d;
vector<ll> v(n);
for (int i = 0; i < n; i ++) {
ll c;
cin >> c;
v[i] = c;
}
auto nv = v;
ll scazi = 0;
for (int i = 0; i < n; i ++) {
nv[i] -= scazi;
scazi += (nv[i] % d + d) % d;
nv[i] -= (nv[i] % d + d) % d;
nv[i] /= d;
v[i] /= d;
}
int q;
cin >> q;
while (q --) {
int l, r;
cin >> l >> r;
l --, r --;
ll minnSuf = inf, ans = 0;
for (int i = r; i >= l; i --) {
minnSuf = min(minnSuf, nv[i]);
ans += nv[i] - minnSuf;
}
if (minnSuf + v[l] - nv[l] < 0)
cout << -1 << '\n';
else
cout << ans << '\n';
}
}
/*
algoritmul de optimizat este astfel:
le faci pe toate cu operatii de tip 1 sa fie 0 modulo d
daca e vreuna negativa atunci nu se poate
imparti totul la d sa fie mai usor
raspunsul este suma tuturor - suma(i : l..r)(min dupa i)
ca sa aflii daca nu se poate poti sa %d la inceput pe toate, apoi un rmq si aflii daca minimul este <= ceva
hai ca bag brutul sa vad exact cum arata
*/
# | 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... |