Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Look at two neighboring window sums. Their difference kills the shared middle terms: .
That difference equation means each residue class modulo is one free variable plus fixed offsets. Do not try to reconstruct the whole array directly; it has degrees of freedom.
If a query interval has length less than , it misses at least one residue class. You can make all seen residue variables very negative and dump the required compensating sum into an unseen residue, so the answer is unbounded.
When the interval has length at least , every residue appears. For each residue , only over queried indices matters.
For a candidate answer , feasibility is just and , so . Thus the answer is ; the remaining problem is fast computation of .
Research used: the official Codeforces statement, the official contest tutorial PDF, and the contest status page confirming accepted C++ submissions for E. The derivation below follows the same intended modulo-class idea, but the text and implementation are original.
Switch to 0-based indexing. The key identity is
So positions with the same index modulo are chained together. Define fixed offsets by
and for every valid ,
Then every valid array can be written as
where are free integers. The only remaining condition is the first window:
That is the whole structure. The array is not uniquely determined; pretending it is would be a classic 2500-rated footgun.
For a query , if , at least one residue class modulo is absent from the interval. Make all residue variables that appear in the query extremely negative, then adjust one absent residue variable to keep . The queried maximum goes to , so print unbounded.
Now assume . Every residue appears. For each residue , define
The query asks for
For a fixed bound , we need , i.e.
There are no lower bounds. Therefore some integer choice of with sum exists iff the maximum possible sum under these upper bounds is at least :
So the minimum integer answer is
Now we only need to compute quickly.
Use a square-root split on .
Small . Build a sparse table over arithmetic progressions with stride :
For query endpoints, write
For residue , its first and last layer inside the query are
One sparse-table RMQ gives . Summing over all residues costs per query.
Large . Let a position be represented as residue and layer : . The number of layers is , which is small when is large. For every pair of layers , precompute prefix sums over residues:
Build these by fixing , expanding , and maintaining current maxima per residue.
For a query with and , residues split into at most three contiguous ranges because changes at and changes at .
If :
If :
Each piece is answered by one prefix-sum subtraction. Empty pieces are ignored.
With threshold , the complexity is
and memory is in the small case or in the large case. The code uses , which is comfortably within the limits for and .
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
ll ceil_div(ll x, ll d) {
if (x >= 0) return (x + d - 1) / d;
return -((-x) / d);
}
int main() {
setIO();
int n, m;
cin >> n >> m;
int sn = n - m + 1;
vector<ll> s(sn);
for (ll &x : s) cin >> x;
vector<ll> w(n, 0);
for (int i = 0; i + m < n; i++) {
w[i + m] = w[i] + s[i + 1] - s[i];
}
int q;
cin >> q;
const int B = 700;
if (m <= B) {
int maxLen = (n + m - 1) / m;
vector<int> lg(maxLen + 1, 0);
for (int i = 2; i <= maxLen; i++) lg[i] = lg[i / 2] + 1;
int K = lg[maxLen] + 1;
const ll NEG = LLONG_MIN / 4;
vector<vector<ll>> st(K, vector<ll>(n, NEG));
st[0] = w;
for (int k = 1; k < K; k++) {
int jump = (1 << (k - 1)) * m;
int span = ((1 << k) - 1) * m;
for (int i = 0; i + span < n; i++) {
st[k][i] = max(st[k - 1][i], st[k - 1][i + jump]);
}
}
while (q--) {
int l, r;
cin >> l >> r;
--l, --r;
if (r - l + 1 < m) {
cout << "unbounded\n";
continue;
}
int L = l / m, a = l % m;
int R = r / m, b = r % m;
ll sumMax = 0;
for (int c = 0; c < m; c++) {
int pl = L + (c < a);
int pr = R - (c > b);
int len = pr - pl + 1;
int k = lg[len];
int left = c + pl * m;
int right = c + (pr - (1 << k) + 1) * m;
sumMax += max(st[k][left], st[k][right]);
}
cout << ceil_div(s[0] + sumMax, m) << '\n';
}
} else {
int layers = (n + m - 1) / m;
vector<ll> row(layers + 1, 0);
ll pairs = 0;
for (int p = 0; p < layers; p++) {
row[p] = pairs;
pairs += layers - p;
}
row[layers] = pairs;
ll width = (ll)m + 1;
vector<ll> pref(pairs * width, 0);
vector<ll> cur(m);
const ll NEG = LLONG_MIN / 4;
for (int p0 = 0; p0 < layers; p0++) {
fill(cur.begin(), cur.end(), NEG);
for (int p1 = p0; p1 < layers; p1++) {
int base = p1 * m;
int upto = min(m, n - base);
for (int c = 0; c < upto; c++) {
cur[c] = max(cur[c], w[base + c]);
}
ll off = (row[p0] + (p1 - p0)) * width;
pref[off] = 0;
for (int c = 0; c < m; c++) {
ll val = (cur[c] == NEG ? 0 : cur[c]);
pref[off + c + 1] = pref[off + c] + val;
}
}
}
auto get_sum = [&](int p0, int p1, int lo, int hi) -> ll {
if (lo > hi || p0 > p1) return 0LL;
ll off = (row[p0] + (p1 - p0)) * width;
return pref[off + hi + 1] - pref[off + lo];
};
while (q--) {
int l, r;
cin >> l >> r;
--l, --r;
if (r - l + 1 < m) {
cout << "unbounded\n";
continue;
}
int L = l / m, a = l % m;
int R = r / m, b = r % m;
ll sumMax = 0;
if (a <= b) {
sumMax += get_sum(L + 1, R, 0, a - 1);
sumMax += get_sum(L, R, a, b);
sumMax += get_sum(L, R - 1, b + 1, m - 1);
} else {
sumMax += get_sum(L + 1, R, 0, b);
sumMax += get_sum(L + 1, R - 1, b + 1, a - 1);
sumMax += get_sum(L, R - 1, a, m - 1);
}
cout << ceil_div(s[0] + sumMax, m) << '\n';
}
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
ll ceil_div(ll x, ll d) {
if (x >= 0) return (x + d - 1) / d;
return -((-x) / d);
}
int main() {
setIO();
int n, m;
cin >> n >> m;
int sn = n - m + 1;
vector<ll> s(sn);
for (ll &x : s) cin >> x;
vector<ll> w(n, 0);
for (int i = 0; i + m < n; i++) {
w[i + m] = w[i] + s[i + 1] - s[i];
}
int q;
cin >> q;
const int B = 700;
if (m <= B) {
int maxLen = (n + m - 1) / m;
vector<int> lg(maxLen + 1, 0);
for (int i = 2; i <= maxLen; i++) lg[i] = lg[i / 2] + 1;
int K = lg[maxLen] + 1;
const ll NEG = LLONG_MIN / 4;
vector<vector<ll>> st(K, vector<ll>(n, NEG));
st[0] = w;
for (int k = 1; k < K; k++) {
int jump = (1 << (k - 1)) * m;
int span = ((1 << k) - 1) * m;
for (int i = 0; i + span < n; i++) {
st[k][i] = max(st[k - 1][i], st[k - 1][i + jump]);
}
}
while (q--) {
int l, r;
cin >> l >> r;
--l, --r;
if (r - l + 1 < m) {
cout << "unbounded\n";
continue;
}
int L = l / m, a = l % m;
int R = r / m, b = r % m;
ll sumMax = 0;
for (int c = 0; c < m; c++) {
int pl = L + (c < a);
int pr = R - (c > b);
int len = pr - pl + 1;
int k = lg[len];
int left = c + pl * m;
int right = c + (pr - (1 << k) + 1) * m;
sumMax += max(st[k][left], st[k][right]);
}
cout << ceil_div(s[0] + sumMax, m) << '\n';
}
} else {
int layers = (n + m - 1) / m;
vector<ll> row(layers + 1, 0);
ll pairs = 0;
for (int p = 0; p < layers; p++) {
row[p] = pairs;
pairs += layers - p;
}
row[layers] = pairs;
ll width = (ll)m + 1;
vector<ll> pref(pairs * width, 0);
vector<ll> cur(m);
const ll NEG = LLONG_MIN / 4;
for (int p0 = 0; p0 < layers; p0++) {
fill(cur.begin(), cur.end(), NEG);
for (int p1 = p0; p1 < layers; p1++) {
int base = p1 * m;
int upto = min(m, n - base);
for (int c = 0; c < upto; c++) {
cur[c] = max(cur[c], w[base + c]);
}
ll off = (row[p0] + (p1 - p0)) * width;
pref[off] = 0;
for (int c = 0; c < m; c++) {
ll val = (cur[c] == NEG ? 0 : cur[c]);
pref[off + c + 1] = pref[off + c] + val;
}
}
}
auto get_sum = [&](int p0, int p1, int lo, int hi) -> ll {
if (lo > hi || p0 > p1) return 0LL;
ll off = (row[p0] + (p1 - p0)) * width;
return pref[off + hi + 1] - pref[off + lo];
};
while (q--) {
int l, r;
cin >> l >> r;
--l, --r;
if (r - l + 1 < m) {
cout << "unbounded\n";
continue;
}
int L = l / m, a = l % m;
int R = r / m, b = r % m;
ll sumMax = 0;
if (a <= b) {
sumMax += get_sum(L + 1, R, 0, a - 1);
sumMax += get_sum(L, R, a, b);
sumMax += get_sum(L, R - 1, b + 1, m - 1);
} else {
sumMax += get_sum(L + 1, R, 0, b);
sumMax += get_sum(L + 1, R - 1, b + 1, a - 1);
sumMax += get_sum(L, R - 1, a, m - 1);
}
cout << ceil_div(s[0] + sumMax, m) << '\n';
}
}
return 0;
}