#include<bits/stdc++.h> using namespace std; #define foru(i,a,b) for(int i=(a); i<=(b); ++i) #define ford(i,a,b) for(int i=(a); i>=(b); --i) #define rep(i,a) for(int i=0; i<(a); ++i) #define sz(a) (int)(a).size() #define all(a) (a).begin(),(a).end() #define bit(s,i) (((s)>>(i))&1) #define ii pair<int,int> #define vi vector<int> #define vii vector<ii> #define fi first #define se second #define ll long long #define eb emplace_back #define pb push_back #define __builtin_popcount __builtin_popcountll #define _ << " " << template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;} template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;} const int N=3e5+5; int n,q; ll d,c[N],ans[N]; vector<ii> que[N]; int stk[N],top; #define lc id<<1 #define rc id<<1|1 ll st[N<<2],lz[N<<2]; void apply(int id, int len, ll val){ lz[id]+=val; st[id]+=val*len; } void down(int id, int len1, int len2){ if(lz[id]==0) return; apply(lc,len1,lz[id]); apply(rc,len2,lz[id]); lz[id]=0; } void upd(int u, int v, ll val, int id=1, int l=1, int r=n){ if(u>r||v<l) return; if(u<=l&&r<=v){ apply(id,r-l+1,val); return; } int mid=(l+r)>>1; down(id,mid-l+1,r-mid); upd(u,v,val,lc,l,mid); upd(u,v,val,rc,mid+1,r); st[id]=st[lc]+st[rc]; } ll get(int u, int v, int id=1, int l=1, int r=n){ if(u>r||v<l) return 0; if(u<=l&&r<=v) return st[id]; int mid=(l+r)>>1; down(id,mid-l+1,r-mid); return get(u,v,lc,l,mid)+get(u,v,rc,mid+1,r); } void solve(){ cin>>n>>d; foru(i,1,n) cin>>c[i]; cin>>q; foru(i,1,q){ int l,r; cin>>l>>r; que[r].eb(l,i); } foru(i,1,n){ auto cur=[&](int x)->ll{ return c[x]-1LL*get(x,x)*d; }; while(top && cur(stk[top])>cur(stk[top]+1)){ ll dec=(cur(stk[top])-cur(stk[top]+1)+d-1)/d; // cout<<(cur(stk[top])- cur(stk[top]+1)+d-1)/d _ dec<<'\n'; upd(stk[top-1]+1, stk[top], dec); // cout<<stk[top-1]+1 _ stk[top] _ dec _ i<<'\n'; --top; } stk[++top]=i; for(auto [l,id]:que[i]){ if(cur(l)>=0) ans[id]=get(l,i);//,cout<<l _ i _ get(l,i)<<'\n'; else ans[id]=-1; } } foru(i,1,q) cout<<ans[i]<<'\n'; } int32_t main(){ #define task "test" if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } cin.tie(0)->sync_with_stdio(0); int tc=1; //cin>>tc; foru(i,1,tc){ solve(); } }

Main.cpp: In function 'int32_t main()':
Main.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~