#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)
void solve();
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
solve();
return 0;
}
int k;
struct node {
int nbl, nbr, val, sz;
};
struct segtree {
int n;
vector<node> t;
segtree(int _n, vector<int>&a) {
n=_n, t.resize(4*n);
build(0, 0, n-1, a);
}
node combine(node l, node r) {
int nb=max(0LL, (l.nbr-r.nbl+k-1)/k);
int val=l.val+r.val-r.sz*nb;
node ans={l.nbl, r.nbr+nb*k, val, l.sz+r.sz};
return ans;
}
void update(int id) {
t[id]=combine(t[id*2+1], t[id*2+2]);
}
void build(int id, int l, int r, vector<int>&a) {
if (l==r) {
t[id]={a[l]%k, a[l]%k, a[l]/k, 1};
return;
}
int mid=(l+r)/2;
build(id*2+1, l, mid, a);
build(id*2+2, mid+1, r, a);
update(id);
}
node query(int id, int l, int r, int ql, int qr) {
if (ql<=l && r<=qr) return t[id];
int mid=(l+r)/2;
if (qr<=mid) return query(id*2+1, l, mid, ql, qr);
if (ql>mid) return query(id*2+2, mid+1, r, ql, qr);
auto L=query(id*2+1, l, mid, ql, min(mid, qr));
auto R=query(id*2+2, mid+1, r, max(mid+1, ql), qr);
return combine(L, R);
}
node query(int l, int r) { return query(0, 0, n-1, l, r); }
};
int n, q;
vector<int> a;
void solve() {
cin >> n >> k;
a.resize(n); for (auto &u: a) cin >> u;
segtree st(n, a);
cin >> q;
while (q--) {
int l, r; cin >> l >> r; l--, r--;
node res=st.query(l, r);
if (res.nbr>a[r]) {
cout << -1 << endl;
continue;
}
int ans=res.val-(r-l+1)*(a[r]-res.nbr)/k;
cout << ans << 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... |