#include <bits/stdc++.h> /* Checklist: - Check statement: - Check filename: - Check test limit: - Stresstest: */ using namespace std; using ll = long long; #define int long long #define pii pair<ll, ll> #define fi first #define se second const ll N = 5e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 19; int n, k; int c[N], a[N]; int q; pii qry[N]; int bad[N], pfs[N]; int R[N]; int up[N][lim + 1], t[N][lim + 1]; struct ST { vector <int> st; ST (int _n) { st.assign(4 * (_n + 5), 0); } void build(int i, int l, int r) { if (l == r) { st[i] = a[l]; return; } int mid = (l + r) / 2; build(2 * i, l, mid); build(2 * i + 1, mid + 1, r); st[i] = min(st[2 * i], st[2 * i + 1]); } int get(int i, int l, int r, int u, int v) { if (u > r || v < l) return inf; if (u <= l && r <= v) return st[i]; int mid = (l + r) / 2; return min(get(2 * i, l, mid, u, v), get(2 * i + 1, mid + 1, r, u, v)); } } st(N); void preprocess() { for (int i = 2; i <= n; i++) { bad[i] = bad[i - 1]; if (c[i] % k < c[i - 1] % k) bad[i]++; } for (int i = 1; i <= n; i++) { a[i] = c[i] - (c[i] % k + bad[i] * k); pfs[i] = pfs[i - 1] + a[i]; } st.build(1, 1, n); // compute previous index (pre) in R[]: previous index with a[pre] <= a[i] (strict pop when >) stack<int> s; for (int i = 1; i <= n; i++) { while (!s.empty() && a[s.top()] > a[i]) s.pop(); R[i] = s.empty() ? 0 : s.top(); // R now stores "pre" s.push(i); up[i][0] = R[i]; t[i][0] = pfs[i] - pfs[R[i]] - (i - R[i]) * a[i]; } for (int lev = 1; lev <= lim; lev++) { for (int j = 1; j <= n; j++) { int mid = up[j][lev - 1]; if (mid == 0) { up[j][lev] = 0; t[j][lev] = t[j][lev - 1]; } else { up[j][lev] = up[mid][lev - 1]; t[j][lev] = t[j][lev - 1] + t[mid][lev - 1]; } } } } signed main() { ios::sync_with_stdio(false); cin.tie(0); if (fopen(".inp", "r")) { freopen(".inp", "r", stdin); freopen(".out", "w", stdout); } cin >> n >> k; for (int i = 1; i <= n; i++) cin >> c[i]; preprocess(); cin >> q; for (int qi = 1; qi <= q; qi++) { int l, r; cin >> l >> r; if (st.get(1, 1, n, l, r) + bad[l] * k < 0) { cout << -1 << '\n'; continue; } long long sum = 0; int cur = r; for (int j = lim; j >= 0; j--) { if (cur == 0) break; if (up[cur][j] != 0 && up[cur][j] >= l) { sum += t[cur][j]; cur = up[cur][j]; } } if (cur != 0 && cur >= l) { sum += pfs[cur] - pfs[l - 1] - (cur - l + 1) * a[cur]; } cout << sum / k << '\n'; } return 0; }

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