#include <bits/stdc++.h>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r)
{
return uniform_int_distribution<ll> (l, r)(rd);
}
const int N = 3e5 + 7;
const int Mod = 998244353;
const int szBL = 916;
const ll INF = 1e9;
const int BASE = 137;
int n, Q;
ll D;
ll a[N];
pair<ll, ll> spt[N][25];
//struct Segment_Tree {
// struct Node {
// ll S, X, Size, L, R;
// }st[N << 2];
//
// void Merge (Node &cur, Node &lf, Node &rt) {
// cur.R = rt.R;
// if (rt.L > lf.R) {
// cur.L = lf.L;
// cur.S = lf.S + rt.S;
// cur.X = lf.X;
// cur.Size = lf.Size;
// }
// else {
// cur.S = ceil(1.0 * (lf.R - rt.L) / D) + lf.X * rt.Size + rt.S + lf.S;
// cur.X = lf.X + rt.X;
// cur.Size =
//
// }
// }
// void build (int id, int l, int r) {
//
// }
//};
void solution() {
cin >> n >> D;
rep (i, 1, n) {
cin >> a[i];
}
// ST.init(n);
for (int j = 1; (1 << j) <= n; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; i ++) {
pair<ll, ll> &cur = spt[i][j], &lf = spt[i][j - 1], &rt = spt[i + (1 << j - 1)][j - 1];
int sz = (1 << j - 1);
// if (i == 1 && j == 2) {
// cout << lf.fs<<","<<lf.se<<" "<<rt.fs<<","<<rt.se <<"\n";
// }
cur.fs = lf.fs + rt.fs + rt.se * sz +
1LL * ceil(1.0 * (a[i + sz - 1] - a[i + sz] + rt.se) / D) * sz;
cur.se = lf.se + rt.se + ceil(1.0 * (a[i + sz - 1] - a[i + sz] + rt.se) / D) ;
}
}
// cout << spt[1][2].fs <<"\n";
// return;
ll Q;
cin >> Q;
rep (q, 1, Q) {
int L, R;
cin >> L >> R;
int st = L;
ll S = 0, X = 0;
reb (i, 20, 0) {
if (st + (1 << i) - 1 <= R) {
S = S + (st - L) * spt[st][i].se + spt[st][i].fs;
X += spt[st][i].se;
if (st > L) {
S = S + ceil(1.0 * (a[st - 1] - a[st] + spt[st][i].se) / D);
X += ceil(1.0 * (a[st - 1] - a[st] + spt[st][i].se) / D);
}
st += (1 << i);
}
}
// cout << a[L] <<" "<< X<<"\n";
if (a[L] - D * X < 0) {
cout << -1 <<"\n";
}
else cout << S <<"\n";
}
}
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// file ("WATERMOV");
int num_Test = 1;
// cin >> num_Test;
while (num_Test--)
solution();
}
/*
6 6 4
2 2 3 6
2 2 6 3
2 4 4 5
4 2 6 4
*/
Compilation message
Main.cpp: In function 'void solution()':
Main.cpp:70:87: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
70 | pair<ll, ll> &cur = spt[i][j], &lf = spt[i][j - 1], &rt = spt[i + (1 << j - 1)][j - 1];
| ~~^~~
Main.cpp:71:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
71 | int sz = (1 << j - 1);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
279 ms |
126768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
9160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
248 ms |
105040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
