#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];
ll 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 + sz * ceil (1.0 * (a[i + sz - 1] - a[i + sz]) / D);
cur.se = lf.se + rt.se + ceil(1.0 * (a[i + sz - 1] - a[i + sz]) / D) ;
// if (i == 1 && j == 2) {
// cout << cur.fs <<" "<<cur.se<<" " <<lf.fs + rt.fs + rt.se * sz<<"\n";
// }
}
}
// 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 + (st - L) *ceil(1.0 * (a[st - 1] - a[st]) / D);
X += ceil(1.0 * (a[st - 1] - a[st]) / 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 4
18 16 12 8 5 3
3
1 4
1 5
2 4
1 4
5
6 7
4 9
1 5
1 5
8 9
*/
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:29: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
71 | ll sz = (1 << j - 1);
| ~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
281 ms |
125968 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
77 ms |
7768 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
250 ms |
104936 KB |
Output is correct |
2 |
Correct |
274 ms |
126548 KB |
Output is correct |
3 |
Correct |
111 ms |
32592 KB |
Output is correct |
4 |
Correct |
283 ms |
129664 KB |
Output is correct |
5 |
Incorrect |
258 ms |
118024 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |