#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=3e5+5;
ll n, d, c[nx], q, l[nx], r[nx], t[nx], qs[nx];
stack<pair<ll, ll>> st;
vector<ll> qrs[nx];
struct segtree
{
ll d[4*nx];
void update(int l, int r, int i, int idx, ll vl)
{
if (idx<l||r<idx) return;
if (l==r) return d[i]=vl, void();
int md=(l+r)/2;
update(l, md ,2*i, idx ,vl);
update(md+1, r ,2*i+1, idx, vl);
d[i]=d[2*i]+d[2*i+1];
}
ll query(int l, int r, int i, int ql, int qr)
{
if (qr<l||r<ql) return 0;
if (ql<=l&&r<=qr) return d[i];
int md=(l+r)/2;
return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
}
} s;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>d;
for (int i=1; i<=n; i++) cin>>c[i];
for (int i=1; i<n; i++) if (c[i]>c[i+1]) t[i]=(c[i]-c[i+1])/d+((c[i]-c[i+1])%d!=0);
for (int i=1; i<n; i++) qs[i]=qs[i-1]+t[i];
for (int i=1; i<n; i++) s.update(1, n, 1, i, t[i]*i);
cin>>q;
for (int i=1; i<=q; i++)
{
cin>>l[i]>>r[i];
if ((qs[r[i]-1]-qs[l[i]-1])*d>c[l[i]]) cout<<-1<<'\n';
else
{
if (l[i]==r[i]) cout<<0<<'\n';
else cout<<s.query(1, n, 1, l[i], r[i]-1)-(l[i]-1)*(qs[r[i]-1]-qs[l[i]-1])<<'\n';
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
8540 KB |
Output is correct |
2 |
Correct |
2 ms |
8540 KB |
Output is correct |
3 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
85 ms |
29196 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
42 ms |
14160 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
156 ms |
22868 KB |
Output is correct |
2 |
Correct |
158 ms |
27772 KB |
Output is correct |
3 |
Correct |
112 ms |
17732 KB |
Output is correct |
4 |
Correct |
174 ms |
27984 KB |
Output is correct |
5 |
Correct |
167 ms |
32632 KB |
Output is correct |
6 |
Correct |
186 ms |
33572 KB |
Output is correct |
7 |
Correct |
169 ms |
27732 KB |
Output is correct |
8 |
Correct |
183 ms |
33356 KB |
Output is correct |
9 |
Correct |
113 ms |
26996 KB |
Output is correct |
10 |
Correct |
84 ms |
26860 KB |
Output is correct |
11 |
Correct |
165 ms |
27988 KB |
Output is correct |
12 |
Correct |
127 ms |
27216 KB |
Output is correct |
13 |
Correct |
180 ms |
33364 KB |
Output is correct |
14 |
Correct |
101 ms |
29268 KB |
Output is correct |
15 |
Correct |
191 ms |
33168 KB |
Output is correct |
16 |
Correct |
95 ms |
29268 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
8540 KB |
Output is correct |
2 |
Correct |
2 ms |
8540 KB |
Output is correct |
3 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |