#include <bits/stdc++.h>
using namespace std;
struct range {
long long startH, endH, cost;
int len;
};
const int MAX_N = 3e5;
const int MAX_LOG_N = 18;
const long long INF = 1e18;
int n;
long long d;
long long a[MAX_N + 1];
range nxt[MAX_LOG_N + 1][MAX_N + 1];
range operator + (range &a, range &b) {
long long delay = 0;
if (b.endH < a.startH)
delay = (a.startH - b.endH + d - 1) / d;
range ans;
ans.startH = b.startH;
ans.endH = a.endH - delay * d;
ans.cost = a.cost + b.cost + delay * a.len;
ans.len = a.len + b.len;
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> d;
for (int i = 1; i <= n; i++)
cin >> a[i];
a[0] = -1;
for (int i = 1; i <= n; i++)
nxt[0][i] = {a[i], a[i], 0, 1};
for (int p = 1; (1 << p) <= n; p++) {
for (int i = (1 << p); i <= n; i++) {
nxt[p][i] = nxt[p - 1][i - (1 << (p - 1))] + nxt[p - 1][i];
//printf("%d %d %lld %lld\n", p, i, nxt[p][i].endH, nxt[p][i].cost);
}
}
int q;
cin >> q;
for (; q > 0; q--) {
int l, r;
cin >> l >> r;
range ans = {a[r], a[r], 0, 1};
r--;
for (int p = log2(n); p >= 0; p--) {
if (r - (1 << p) + 1 >= l) {
ans = nxt[p][r] + ans;
r -= (1 << p);
}
}
cout << (ans.endH < 0 ? -1 : ans.cost) << "\n";
}
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... |