#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> ii;
const ll INF=1e18;
template<typename U, typename V>
ostream &operator<<(ostream &os, const pair<U, V> &p){
return os<<"("<<p.fst<<", "<<p.snd<<")";
}
template<typename T>
ostream &operator<<(ostream &os, const set<T> &s){
os<<"{";
bool flag=false;
for(const T &x:s){
if(flag) cout<<", ";
flag=true;
os<<x;
}
return os<<"}";
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
os<<"[";
bool flag=false;
for(const T &x:v){
if(flag) cout<<", ";
flag=true;
os<<x;
}
return os<<"]";
}
ll d;
const int SZ=1<<19;
struct Node{
vll vals;
vll mini;
vll suff;
ll cost=0LL;
Node(){}
Node(vll v){
if(v.empty()) return;
vals=v;
int n=sz(v);
mini.resize(n),suff.resize(n);
mini[n-1]=suff[n-1]=vals[n-1];
dforn(i,n-1){
mini[i]=min(mini[i+1],vals[i]);
cost+=vals[i]-mini[i];
suff[i]=suff[i+1]+mini[i];
}
}
};
Node st[2*SZ];
ll query(int l, int r){
vi left,right;
for(l+=SZ,r+=SZ;l<r;l/=2,r/=2){
if(l&1) left.pb(l++);
if(r&1) right.pb(--r);
}
vi nodes=left;
dforn(i,sz(right)) nodes.pb(right[i]);
ll mini=INF;
ll cost=0;
reverse(all(nodes));
for(int u:nodes){
int lo=-1,hi=sz(st[u].mini);
while(hi-lo>1){
int mid=(lo+hi)/2;
if(st[u].mini[mid]>=mini) hi=mid;
else lo=mid;
}
cost+=st[u].cost;
if(hi!=sz(st[u].mini))cost+=st[u].suff[hi]-mini*(sz(st[u].mini)-hi);
mini=min(mini,st[u].mini.front());
}
return cost;
}
struct Node2{
bool flag=false;
ll mini=INF,maxi=-INF;
int cnt=0;
ll cost=0;
Node2(){
flag=true;
}
Node2(ll x){
cnt=1;
mini=maxi=x;
cost=0;
flag=false;
}
};
Node2 merge(Node2 &a, Node2 &b){
if(a.flag) return b;
if(b.flag) return a;
Node2 c;
ll diff=a.maxi-b.mini;
ll k=max((diff+d-1)/d,0LL);
c.maxi=b.maxi;
assert(a.maxi-d*k<=b.mini);
c.mini=a.mini-d*k;
c.cnt=a.cnt+b.cnt;
c.cost=a.cost+b.cost+k*a.cnt;
c.flag=false;
return c;
}
Node2 st2[2*SZ];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n>>d;
vll c(n);
forn(i,n){
cin>>c[i];
}
int q;
cin>>q;
if(n<=3000&&q<=3000){
forn(_,q){
int l,r;
cin>>l>>r;
--l;
ll mini=INF;
ll cost=0;
dforsn(i,l,r){
ll k=max((c[i]-mini+d-1)/d,0LL);
cost+=k;
assert(c[i]-k*d<=mini);
mini=c[i]-k*d;
}
if(mini<0) cout<<"-1\n";
else cout<<cost<<'\n';
}
return 0;
}
bool flag=true;
forn(i,n-1) flag&=c[i]>=c[i+1];
if(!flag){
forn(i,n) st[i+SZ]=vll{c[i]};
dforsn(i,1,SZ){
vll v=st[2*i].vals;
forn(j,sz(st[2*i+1].vals)) v.pb(st[2*i+1].vals[j]);
st[i]=v;
}
forn(_,q){
int l,r;
cin>>l>>r;
--l;
cout<<query(l,r)<<'\n';
}
return 0;
}
forn(i,n){
st2[i+SZ]=c[i];
}
dforsn(i,1,SZ){
st2[i]=merge(st2[2*i],st2[2*i+1]);
}
forn(_,q){
Node2 left,right;
int l,r;
cin>>l>>r;
for(l+=SZ-1,r+=SZ;l<r;l/=2,r/=2){
if(l&1) left=merge(left,st2[l++]);
if(r&1) right=merge(st2[--r],right);
}
Node2 ret=merge(left,right);
if(ret.mini<0) cout<<"-1\n";
else cout<<ret.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... |