/*
.... ...::--::::::..
.-+*#%%%%%%%*++=#%@@%%%%@@@%%%%%#+-:
-*%%%%%%@%%%%@@@%%@@@@@@@@@@%%@@@%%%%##%#*-
:*@%%@@@@@@%%@@@@@@@@@@@@@@@@@@@@%@@@@@%%%%%%%#-
-#@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@%%@@@@@%%%%%%%#:
.*@%%@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@%@@@%%@@@@%%@%%%%@+
-#%@%@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@%%@@@@@@@@%@@@%%%@+
-%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@%%@@@@@@@@@@@@%%%@+
.%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%@@@@@@@%@@@@@@@@+
.%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%@@@%@@%@@@@%@@@@=
#@%@@@@@@@@@@@@@@@@@%%@@%%%%%%%%%%%%@%@%%%%@%%%%@%@@%%%@%%%@@%%.
=@%@@@@@@@@@@@@@@@@@%%%%%%%%#%%%%%%%%%%%%%%%%%%@%%@@@@@%@%%%%@@%%.
.@%%@%@@@@@@@@@@@%@%%%%#%%%##+**%%%%#%%%%###%%%%%%%@%%@@%%%%%%@@@@.
-@%%%@@@@@@@@@@%%%%%%%#*#%#*++=++****++++++**#%###%@@@%@%%@%%%%@@@-
-@%%@@@@@@@@@@%%#####%*+++====-=====------===+++=++#%@@@%%@%%%%%%%=
.@%@%%@@@@@@@%##**+*+++==-----------------------===+*%%%@%%%%%%%%#.
*@@@%@%@@@%#***+***++==--------------------===++===+#%%@@%%%%%%+-
-%@@%@%@@%#****###%%%%#*+===---------==+**####**+++++#%%%%%%%%%:
#@@%@%@%#*+++++++++++***+++===----===+++++========+++#%@%%%%%-
-@@%@@@#+=+++++++=======++===-----=====++============+#@%%%@*
.@@@@%@*===++**#*#@#%#++====-------===++#@%@**#*++==--+@%%%#:
.##%@%%*====++**+=*#*-=++--=---------=+==+*+======----=@%*==-
++*#%%+==============-----=---:----------------------=%%==+=
.+=+*%+==-----------:--------:::-----:::-----::::-----%#--=.
-=+*%*===--------::::-------:::-::-:::::::::::::----=%+=-:
==+%#===------::::::--==---::::----::::::::::::----+#==:
:++*#===--------:::---=----::::::--::::::::::::----++=-
-=+#+===-------:--:-=-====---==---:::::::::::-----+--
==++=====-------:--=+***+++++**+-:::::::::------==-.
.==+====------------=++=========-::::::--------==::
=====----------=========------:::::-------==
+======----=======----------------------==-
:+==========++++**+=++===+++++=--------==+.
=+==========***++=========++=--------===:
=++=========++++==----=====-----======-
-+++==========+++++++++==-----=======+:
:*+++++=============--------==========:
.*+**++++=======-----------======+++==:
+++*****++++=================++++====:
:++++++*****++++++++++++==++++++======-
=%=+++++++******************+++====--===*-
-%%=======+++++++++++++++++=======-----=-+#-
-*%@++======++++++++==============------==+%*:
=+*#%*+=======+++++++++==-========------===*#*+-
.:****#%#*+========++++++++++=======------===+##++==-:.
.-=+**#*#***##*++========================---======*#**++*++*++=-.
.-=+##***#####***###*++==============-=--=====--======+#**+++++++*+++**+=:
.-=*#####*##########*####*++==============--=============+#*#**++++++*****+*+**+-.
.-+*#####################*#####+++==========================+***#****+++*+***********++=
+###################*#############*++========================*#*******++++++*******+******
####################*#############%**+===-===========--=====*#**#**+++++++++**************
###########################*##%@%%@%#*+=-----====--------=+*##*#@@@%#*++++++**************
########################**#%@@%%%%%%#%%#*=--------------+***#*#@%@@%%@%#++++***###********
######################**#%%%%%%%%%%%%%%%%%#+--::::---=+#**###%@%%%%%%%%%@***#####***+*****
^^pavement for goodluck
*/
//Beichen is a classic problem in China
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
#define int long long
#define test cout<<"test\n"<<flush;
#define endl "\n"
#define iloop(a,b) for(int i=a;i!=b;i+=(2*((int)(a<b))-1))
#define jloop(a,b) for(int j=a;j!=b;j+=(2*((int)(a<b))-1))
#define kloop(a,b) for(int k=a;k!=b;k+=(2*((int)(a<b))-1))
#define lloop(a,b) for(int l=a;l!=b;l+=(2*((int)(a<b))-1))
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define pii pair<int,int>
#define hashmap unordered_map
#define coutpair(p) cout<<p.first<<" "<<p.second<<endl;
#define couttrip(a,b,c) cout<<a<<" "<<b<<" "<<c<<" ";
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define flip(p) {p.second,p.first}
#define lsb(x) x&-x
#define debug(x) cout<<x<<flush
#define decimal(x) fixed<<setprecision(x)
#define sf(x) setprecision(x)
#define mod(x,k) (((x%k)+k)%k)
#define reset(a,v) for(auto &it:a){it=v;}
#define inf 1e16
#define neginf -1e16
pair<int,int> rev(pair<int,int> p){return {p.second,p.first};}
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
//lb returns larger, ub returns larger or equals if set sorts backwards
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
struct node{
int s,e,mid;
int mini,sum;
node *l,*r;
node(int S,int E){
s=S,e=E;
mid=(S+E)/2;
mini=0,sum=0;
if(s!=e){
l=new node(s,mid);
r=new node(mid+1,e);
}
}
void update(int P,int V){
if(s==e){
mini=V,sum=V;
return;
}
if(P<=mid){
l->update(P,V);
} else{
r->update(P,V);
}
mini=min(l->mini,r->mini);
sum=l->sum+r->sum;
}
int minquery(int S,int E){
if(s==S and e==E){
return mini;
}
if(E<=mid){
return l->minquery(S,E);
} else if(S>mid){
return r->minquery(S,E);
} else{
return min(l->minquery(S,mid),r->minquery(mid+1,E));
}
}
int sumquery(int S,int E){
if(s==S and e==E){
return sum;
}
if(E<=mid){
return l->sumquery(S,E);
} else if(S>mid){
return r->sumquery(S,E);
} else{
return l->sumquery(S,mid)+r->sumquery(mid+1,E);
}
}
} *root;
struct node1{
int s,e,mid;
int mini;
node1 *l,*r;
node1(int S,int E){
s=S,e=E;
mid=(S+E)/2;
mini=0;
if(s!=e){
l=new node1(s,mid);
r=new node1(mid+1,e);
}
}
void update(int P,int V){
if(s==e){
mini=V;
return;
}
if(P<=mid){
l->update(P,V);
} else{
r->update(P,V);
}
mini=min(l->mini,r->mini);
}
int query(int S,int E){
if(s==S and e==E){
return mini;
}
if(E<=mid){
return l->query(S,E);
} else if(S>mid){
return r->query(S,E);
} else{
return min(l->query(S,mid),r->query(mid+1,E));
}
}
} *root2;
signed main(){
fastio;
int n,d;
cin>>n>>d;
int a[n];
iloop(0,n){
cin>>a[i];
}
int b[n];
b[n-1]=0;
iloop(n-2,-1){
int prev=a[i+1]-d*b[i+1];
b[i]=(int)(max(a[i]-prev,0LL)+d-1)/d;
}
root=new node(0,n-1);
root2=new node1(0,n-1);
iloop(0,n){
root->update(i,b[i]);
root2->update(i,a[i]-d*b[i]);
//cout<<b[i]<<" ";
}
//cout<<endl;
int q;
cin>>q;
iloop(0,q){
int a,b;
cin>>a>>b;
a--,b--;
int x=root->minquery(a,b);
int y=root2->query(a,b);
//cout<<x<<" "<<y<<" ";
if(y+d*x<0){
cout<<-1<<endl;
} else{
cout<<root->sumquery(a,b)-(b-a+1)*x<<endl;;
}
}
}
# | 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... |