#include<bits/stdc++.h>
#define ll long long
#define pi pair<int,int>
#define fi first
#define se second
#define maxn 300005
using namespace std;
int n;
ll d;
ll a[maxn];
ll b[maxn];
ll sb[maxn];
ll dif[maxn];
ll sdif[maxn];
int pre[maxn];
int lg[maxn];
ll rmq[maxn][20];
ll get_minB(int l,int r)
{
int k=__lg(r-l+1);
return min(rmq[l][k],rmq[r-(1<<k)+1][k]);
}
struct
{
int nho[4*maxn];
ll lazy[4*maxn];
ll s[4*maxn];
void Push_down(int r,int lo,int hi)
{
int mid=(lo+hi)/2;
if(nho[r])
{
nho[2*r]=1;
lazy[2*r]=lazy[r];
s[2*r]=lazy[r]*(mid-lo+1);
nho[2*r+1]=1;
lazy[2*r+1]=lazy[r];
s[2*r+1]=lazy[r]*(hi-mid);
nho[r]=0;
lazy[r]=0;
}
}
void update(int u,int v,ll val,int r=1,int lo=1,int hi=n)
{
if(u>hi||v<lo)return;
if(u<=lo&&hi<=v)
{
s[r]=(hi-lo+1)*val;
nho[r]=1;
lazy[r]=val;
return;
}
int mid=(lo+hi)/2;
Push_down(r,lo,hi);
update(u,v,val,2*r,lo,mid);
update(u,v,val,2*r+1,mid+1,hi);
s[r]=s[2*r]+s[2*r+1];
}
ll get(int u,int v,int r=1,int lo=1,int hi=n)
{
if(u>hi||v<lo)return 0;
if(u<=lo&&hi<=v)return s[r];
int mid=(lo+hi)/2;
Push_down(r,lo,hi);
return get(u,v,2*r,lo,mid)+get(u,v,2*r+1,mid+1,hi);
}
}tree;
vector<pi>Q[maxn];
ll ans[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>d;
lg[1]=0;
for(int i=2;i<=n;i++)
{
lg[i]=lg[i/2]+1;
}
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
dif[i]=((a[i+1]-a[i])%d+d)%d;
sdif[i]=sdif[i-1]+dif[i];
b[i]=rmq[i][0]=(a[i]-sdif[i-1]);
sb[i]=sb[i-1]+b[i];
}
for(int i=1;i<=n;i++)
{
int j=i-1;
while(j>=1&&b[j]>=b[i])j=pre[j];
pre[i]=j;
}
for(int k=1;k<=lg[n]+1;k++)
{
for(int i=1;i+(1<<k)-1<=n;i++)
{
rmq[i][k]=min(rmq[i][k-1],rmq[i+(1<<(k-1))][k-1]);
}
}
int q;
cin>>q;
for(int i=1;i<=q;i++)
{
int l,r;
cin>>l>>r;
if(get_minB(l,r)<-(sdif[l-1]-a[l]%d))
{
ans[i]=-1;
continue;
}
Q[r].push_back({l,i});
}
for(int i=1;i<=n;i++)
{
tree.update(pre[i]+1,i,b[i]);
for(auto[l,id]:Q[i])
{
ans[id]=((sb[i]-sb[l-1])-tree.get(l,i))/d;
}
}
for(int i=1;i<=q;i++)
{
cout<<ans[i]<<'\n';
}
}
/*
s[i]=s[i-3]+(a[i-2]-s[i-3])%mod+(a[i-1]-a[i-2])%mod+(a[i]-a[i-1])%mod
s[i]=(a[l])%mod+(a[l+1]-a[l])%mod+...+(a[i]-a[i-1])%mod
(a[i]-sdif[i-1])+(sdif[l-1]-a[l]%d)
Voi mot thang r co dinh thi tat cac so chi cong
len mot luong co dinh
(a[i]-sdif[i-1])+(sdif[l-1]-a[l]%d)>=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... |