#include <bits/stdc++.h>
using namespace std;
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], sumA[MAX_N + 1];
long long c[MAX_N + 1];
int nxt[MAX_LOG_N + 1][MAX_N + 1];
long long cost[MAX_LOG_N + 1][MAX_N + 1];
long long getCost(int l, int r) {
return (sumA[r] - sumA[l - 1] - a[r] * (r - l + 1)) / d;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> d;
for (int i = 1; i <= n; i++)
cin >> c[i];
for (int i = n; i >= 1; i--)
a[i] = (c[i] + a[i + 1] - c[i + 1] + d - 1) / d * d;
a[0] = -1;
for (int i = 1; i <= n; i++)
sumA[i] = sumA[i - 1] + a[i];
//for (int i = 1; i <= n; i++)
//printf("%d %lld\n", i, a[i]);
vector<int> st;
st.push_back(0);
for (int i = 1; i <= n; i++) {
while (a[i] <= a[st.back()])
st.pop_back();
nxt[0][i] = st.back();
cost[0][i] = getCost(nxt[0][i] + 1, i);
st.push_back(i);
}
for (int p = 1; (1 << p) <= n; p++) {
for (int i = 1; i <= n; i++) {
nxt[p][i] = nxt[p - 1][nxt[p - 1][i]];
cost[p][i] = cost[p - 1][i] + cost[p - 1][nxt[p - 1][i]];
}
}
int q;
cin >> q;
for (; q > 0; q--) {
int l, r;
cin >> l >> r;
/*
long long extra = (a[l] - c[l]) - (a[r] - c[r]);
//printf("%lld\n", extra);
if (c[l] < extra) {
cout << "-1\n";
continue;
}
*/
long long ans = 0;
for (int p = log2(n); p >= 0; p--) {
if (nxt[p][r] >= l) {
ans += cost[p][r];
r = nxt[p][r];
}
}
ans += getCost(l, r);
cout << ans << "\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... |