These are the notes for Competitive Programming episode 70. A monotonic stack is a stack of indices whose values stay sorted; a monotonic deque is the same thing with an expiring front. Both turn many O(n²) contest problems into O(n), because every index is pushed once and popped at most once (amortised analysis). Cold Streaks (the sum of the minimum of every subarray) uses contribution counting with nearest-smaller indices, and a real tie-breaking bug that passes the sample but fails a stress test (8 instead of 6 on 2 2). Calm Window (the longest window with max − min ≤ d) uses two pointers with two monotonic deques, and a real infinite loop (TLE on an 8-number sample) when expired indices aren't dropped. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook
Walk down a street of shops, each with a price, and at every shop ask: where is the nearest cheaper shop behind me? When a new, cheap shop opens, every shop behind it that is at least as expensive can never be anyone's answer again: for every later shop, the new one is both closer and cheaper. Throw those away. What's left is a short list whose prices fall as you look back, and its top is the answer. Each shop joins the list once and leaves once: linear time. That list is a monotonic stack.
Problem R1 · Cold Streaks
(Written for this course.)
- n daily temperatures a1..an (n ≤ 10^6, 1 ≤ ai ≤ 10^6).
- For every period l..r of consecutive days, take its coldest temperature. Print the sum over all periods.
- The answer can reach about 5·10^17: use
long long.
4
3 1 2 4
Periods from day 1: 3, 1, 1, 1; from day 2: 1, 1, 1; then 2, 2; then 4. Total 17.
Attempt 1: every period (TLE)
The brute force is kept as the checker for the stress test.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll brute(const vector<ll>& a) { // every period l..r
int n = a.size();
ll total = 0;
for (int l = 0; l < n; l++) {
ll mn = a[l];
for (int r = l; r < n; r++) {
mn = min(mn, a[r]); // coldest day of l..r
total += mn;
}
}
return total;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> a(n);
for (auto& x : a) cin >> x;
cout << brute(a) << "\n";
}
17
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll brute(const vector<ll>& a) { // every period l..r
int n = a.size();
ll total = 0;
for (int l = 0; l < n; l++) {
ll mn = a[l];
for (int r = l; r < n; r++) {
mn = min(mn, a[r]); // coldest day of l..r
total += mn;
}
}
return total;
}
int main() {
int n = 1000000; // a million days
mt19937 gen(70);
vector<ll> a(n);
for (auto& x : a) x = gen() % 1000000 + 1;
cout << brute(a) << "\n";
}
Time Limit Exceeded
About n²/2 = 5·10^11 periods.
The key observation: count contributions
Turn the sum around: for every day i, count the periods in which a[i] is the minimum.
- L[i] = the nearest colder day on the left, R[i] = the nearest colder day on the right.
- The period may start at L+1..i and end at i..R−1: (i − L)·(R − i) periods.
- answer = Σ a[i]·(i − L[i])·(R[i] − i). In the sample, the
1on day 2 has no colder day anywhere: 2 starts × 3 ends = 6 periods, contributing 6.
The monotonic stack
- Left to right: while the top is ≥ a[i], pop; L[i] = the top (or −1); push i.
- Right to left: the same gives R[i] (or n).
- The stack holds indices whose values increase from bottom to top. n pushes and at most n pops: O(n) even with a
whileinside thefor.
Bug: strict on both sides (passes the sample!)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll fast(const vector<ll>& a) {
int n = a.size();
vector<int> L(n), R(n), st;
for (int i = 0; i < n; i++) { // previous strictly colder day
while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
L[i] = st.empty() ? -1 : st.back();
st.push_back(i);
}
st.clear();
for (int i = n - 1; i >= 0; i--) { // next strictly colder day
while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
R[i] = st.empty() ? n : st.back();
st.push_back(i);
}
ll total = 0;
for (int i = 0; i < n; i++) total += a[i] * (i - L[i]) * (R[i] - i);
return total;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> a(n);
for (auto& x : a) cin >> x;
cout << fast(a) << "\n";
}
17
The sample passes. A stress test with values 1..3 (lots of ties), which prints the failing input:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll brute(const vector<ll>& a) { // every period l..r
int n = a.size();
ll total = 0;
for (int l = 0; l < n; l++) {
ll mn = a[l];
for (int r = l; r < n; r++) {
mn = min(mn, a[r]); // coldest day of l..r
total += mn;
}
}
return total;
}
ll fast(const vector<ll>& a) {
int n = a.size();
vector<int> L(n), R(n), st;
for (int i = 0; i < n; i++) { // previous strictly colder day
while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
L[i] = st.empty() ? -1 : st.back();
st.push_back(i);
}
st.clear();
for (int i = n - 1; i >= 0; i--) { // next strictly colder day
while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
R[i] = st.empty() ? n : st.back();
st.push_back(i);
}
ll total = 0;
for (int i = 0; i < n; i++) total += a[i] * (i - L[i]) * (R[i] - i);
return total;
}
int main() {
mt19937 gen(7);
for (int t = 1; t <= 500; t++) {
int n = gen() % 5 + 1;
vector<ll> a(n);
for (auto& x : a) x = gen() % 3 + 1; // tiny values: lots of ties
if (brute(a) != fast(a)) {
cout << "mismatch on test " << t << ": ";
for (ll x : a) cout << x << " ";
return 0;
}
}
cout << "all 500 tests passed";
}
mismatch on test 3: 3 3 2
Shrink it to two equal days, 2 2:
8
The periods are 2, 2 and 2 2: 6. The period 2 2 has two coldest days, and both claimed it: counted twice.
The fix: break ties one way
Strictly colder on the left (pop while >=), colder or equal on the right (pop while >). Each day's periods now stop before the next equal day on its right, so a period with several equal minimums belongs to exactly one of them (the rightmost).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll fast(const vector<ll>& a) {
int n = a.size();
vector<int> L(n), R(n), st;
for (int i = 0; i < n; i++) { // previous strictly colder day
while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
L[i] = st.empty() ? -1 : st.back();
st.push_back(i);
}
st.clear();
for (int i = n - 1; i >= 0; i--) { // next colder-or-equal day
while (!st.empty() && a[st.back()] > a[i]) st.pop_back();
R[i] = st.empty() ? n : st.back();
st.push_back(i);
}
ll total = 0;
for (int i = 0; i < n; i++) total += a[i] * (i - L[i]) * (R[i] - i);
return total;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> a(n);
for (auto& x : a) cin >> x;
cout << fast(a) << "\n";
}
6
17
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll fast(const vector<ll>& a) {
int n = a.size();
vector<int> L(n), R(n), st;
for (int i = 0; i < n; i++) { // previous strictly colder day
while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
L[i] = st.empty() ? -1 : st.back();
st.push_back(i);
}
st.clear();
for (int i = n - 1; i >= 0; i--) { // next colder-or-equal day
while (!st.empty() && a[st.back()] > a[i]) st.pop_back();
R[i] = st.empty() ? n : st.back();
st.push_back(i);
}
ll total = 0;
for (int i = 0; i < n; i++) total += a[i] * (i - L[i]) * (R[i] - i);
return total;
}
int main() {
int n = 1000000; // a million days
mt19937 gen(70);
vector<ll> a(n);
for (auto& x : a) x = gen() % 1000000 + 1;
cout << fast(a) << "\n";
}
13073683325672
A few hundredths of a second for a million days. The stress test now passes:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll brute(const vector<ll>& a) { // every period l..r
int n = a.size();
ll total = 0;
for (int l = 0; l < n; l++) {
ll mn = a[l];
for (int r = l; r < n; r++) {
mn = min(mn, a[r]); // coldest day of l..r
total += mn;
}
}
return total;
}
ll fast(const vector<ll>& a) {
int n = a.size();
vector<int> L(n), R(n), st;
for (int i = 0; i < n; i++) { // previous strictly colder day
while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
L[i] = st.empty() ? -1 : st.back();
st.push_back(i);
}
st.clear();
for (int i = n - 1; i >= 0; i--) { // next colder-or-equal day
while (!st.empty() && a[st.back()] > a[i]) st.pop_back();
R[i] = st.empty() ? n : st.back();
st.push_back(i);
}
ll total = 0;
for (int i = 0; i < n; i++) total += a[i] * (i - L[i]) * (R[i] - i);
return total;
}
int main() {
mt19937 gen(7);
for (int t = 1; t <= 500; t++) {
int n = gen() % 5 + 1;
vector<ll> a(n);
for (auto& x : a) x = gen() % 3 + 1; // tiny values: lots of ties
if (brute(a) != fast(a)) {
cout << "mismatch on test " << t << ": ";
for (ll x : a) cout << x << " ";
return 0;
}
}
cout << "all 500 tests passed";
}
all 500 tests passed
Problem R2 · Calm Window
(Written for this course.)
- The same kind of temperature list and a number d (n ≤ 10^6, 0 ≤ ai, d ≤ 10^9).
- Print the length of the longest period l..r with max − min ≤ d.
8 2
5 6 4 7 6 6 5 9
With d = 2 the longest calm window is 7 6 6 5: 4.
Attempt 1: extend every start (TLE)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int brute(const vector<ll>& a, ll d) {
int n = a.size(), best = 0;
for (int l = 0; l < n; l++) {
ll mn = a[l], mx = a[l];
for (int r = l; r < n; r++) {
mn = min(mn, a[r]), mx = max(mx, a[r]);
if (mx - mn > d) break;
best = max(best, r - l + 1);
}
}
return best;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll d;
cin >> n >> d;
vector<ll> a(n);
for (auto& x : a) cin >> x;
cout << brute(a, d) << "\n";
}
4
With d = 10^9 every window is calm, so every start runs to the end:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int brute(const vector<ll>& a, ll d) {
int n = a.size(), best = 0;
for (int l = 0; l < n; l++) {
ll mn = a[l], mx = a[l];
for (int r = l; r < n; r++) {
mn = min(mn, a[r]), mx = max(mx, a[r]);
if (mx - mn > d) break;
best = max(best, r - l + 1);
}
}
return best;
}
int main() {
int n = 1000000;
ll d = 1000000000; // every window is calm
mt19937 gen(70);
vector<ll> a(n);
for (auto& x : a) x = gen() % 1000000001;
cout << brute(a, d) << "\n";
}
Time Limit Exceeded
Two pointers + two monotonic deques
- A window inside a calm window is calm, so two pointers work: move r right; while the window is too wide, move l right. Both pointers only move forward.
mx: indices with values falling from front to back; its front is the window maximum. Before pushing r, pop every back index whose value is ≤ a[r].mn: indices with values rising; its front is the window minimum.- When l passes an index at a front, that day has left the window: pop it from the front.
Bug: never dropping expired indices (TLE on the sample)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int fast(const vector<ll>& a, ll d) {
int n = a.size(), best = 0, l = 0;
deque<int> mx, mn; // indices: values falling / rising
for (int r = 0; r < n; r++) {
while (!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
while (!mn.empty() && a[mn.back()] >= a[r]) mn.pop_back();
mx.push_back(r), mn.push_back(r);
while (a[mx.front()] - a[mn.front()] > d) { // too hot: shrink
l++;
}
best = max(best, r - l + 1);
}
return best;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll d;
cin >> n >> d;
vector<ll> a(n);
for (auto& x : a) cin >> x;
cout << fast(a, d) << "\n";
}
Time Limit Exceeded
On an 8-number input a TLE can't be slowness: it's an infinite loop. The fronts never change, so a[mx.front()] - a[mn.front()] > d stays true forever and l runs away.
The fix
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int fast(const vector<ll>& a, ll d) {
int n = a.size(), best = 0, l = 0;
deque<int> mx, mn; // indices: values falling / rising
for (int r = 0; r < n; r++) {
while (!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
while (!mn.empty() && a[mn.back()] >= a[r]) mn.pop_back();
mx.push_back(r), mn.push_back(r);
while (a[mx.front()] - a[mn.front()] > d) { // too hot: shrink
l++;
if (mx.front() < l) mx.pop_front(); // drop days that left
if (mn.front() < l) mn.pop_front();
}
best = max(best, r - l + 1);
}
return best;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll d;
cin >> n >> d;
vector<ll> a(n);
for (auto& x : a) cin >> x;
cout << fast(a, d) << "\n";
}
Sample, one day with d = 0, five equal days with d = 0:
4
1
5
The test that killed the brute force:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int fast(const vector<ll>& a, ll d) {
int n = a.size(), best = 0, l = 0;
deque<int> mx, mn; // indices: values falling / rising
for (int r = 0; r < n; r++) {
while (!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
while (!mn.empty() && a[mn.back()] >= a[r]) mn.pop_back();
mx.push_back(r), mn.push_back(r);
while (a[mx.front()] - a[mn.front()] > d) { // too hot: shrink
l++;
if (mx.front() < l) mx.pop_front(); // drop days that left
if (mn.front() < l) mn.pop_front();
}
best = max(best, r - l + 1);
}
return best;
}
int main() {
int n = 1000000;
ll d = 1000000000; // every window is calm
mt19937 gen(70);
vector<ll> a(n);
for (auto& x : a) x = gen() % 1000000001;
cout << fast(a, d) << "\n";
}
1000000
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int brute(const vector<ll>& a, ll d) {
int n = a.size(), best = 0;
for (int l = 0; l < n; l++) {
ll mn = a[l], mx = a[l];
for (int r = l; r < n; r++) {
mn = min(mn, a[r]), mx = max(mx, a[r]);
if (mx - mn > d) break;
best = max(best, r - l + 1);
}
}
return best;
}
int fast(const vector<ll>& a, ll d) {
int n = a.size(), best = 0, l = 0;
deque<int> mx, mn; // indices: values falling / rising
for (int r = 0; r < n; r++) {
while (!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
while (!mn.empty() && a[mn.back()] >= a[r]) mn.pop_back();
mx.push_back(r), mn.push_back(r);
while (a[mx.front()] - a[mn.front()] > d) { // too hot: shrink
l++;
if (mx.front() < l) mx.pop_front(); // drop days that left
if (mn.front() < l) mn.pop_front();
}
best = max(best, r - l + 1);
}
return best;
}
int main() {
mt19937 gen(7);
for (int t = 1; t <= 500; t++) {
int n = gen() % 10 + 1;
ll d = gen() % 4;
vector<ll> a(n);
for (auto& x : a) x = gen() % 6;
if (brute(a, d) != fast(a, d)) { cout << "mismatch on test " << t; return 0; }
}
cout << "all 500 tests passed";
}
all 500 tests passed
Complexity vs the constraints
| Method | Time | Verdict (n = 10^6) |
|---|---|---|
| R1: every period | O(n²) ≈ 5·10^11 | TLE |
| R1: contributions + monotonic stack | O(n) | accepted (~0.04 s) |
| R2: extend every start | O(n²) | TLE |
| R2: two pointers + two deques | O(n) | accepted (~0.03 s) |
Memory: a few arrays of n. Each index is pushed once and popped at most once from each stack/deque, so the inner while loops run at most n times in total (amortised O(1) per step).
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| strict comparison on both sides | 8 instead of 6 on 2 2 |
ties counted twice | >= on one side, > on the other |
| never dropping expired fronts | Time Limit Exceeded on an 8-number sample |
the shrink loop never ends | pop the front when its index < l |
| storing values instead of indices | Wrong Answer | can't tell when an element left the window | store indices |
int products |
Wrong Answer (overflow) | the answer reaches ~10^17 | long long |
popping > instead of >= on the left as well |
Wrong Answer with ties | ties end up claimed by nobody or twice | write the tie rule down first |
front() on an empty deque |
Runtime Error | no element | push r before reading the fronts |
Mini project
Write a generic MonotonicQueue<T, Compare> with push(index, value), expire(l) and best(), and use it to print the maximum and the minimum of every window of size k. Stress test it against a brute force with many equal values.
Practice
These are the homework problems from the episode.
1. Sum of (max − min) over all subarrays. It equals (sum of maxima) − (sum of minima). The sum of maxima is the sum of minima of −a, negated.
2. Largest rectangle in a histogram. For every bar, the widest span where it is the lowest is between its nearest lower bars on both sides: one monotonic stack pass with a sentinel 0 at the end.
Solutions for 1 and 2 (checked against brute force on 100 random tests)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// sum over all subarrays of (max − min) = (sum of maxima) − (sum of minima)
ll contribution(vector<ll> a) { // sum of minima
int n = a.size();
vector<int> L(n), R(n), st;
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
L[i] = st.empty() ? -1 : st.back();
st.push_back(i);
}
st.clear();
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && a[st.back()] > a[i]) st.pop_back();
R[i] = st.empty() ? n : st.back();
st.push_back(i);
}
ll total = 0;
for (int i = 0; i < n; i++) total += a[i] * (i - L[i]) * (R[i] - i);
return total;
}
int main() {
int n;
cin >> n;
vector<ll> a(n), neg(n);
for (int i = 0; i < n; i++) cin >> a[i], neg[i] = -a[i];
ll sumMin = contribution(a), sumMax = -contribution(neg); // max(a) = −min(−a)
cout << sumMax - sumMin << "\n";
}
3
1 3 2
5
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() { // largest rectangle in a histogram
int n;
cin >> n;
vector<ll> h(n);
for (auto& x : h) cin >> x;
vector<int> st; // indices, heights rising
ll best = 0;
for (int i = 0; i <= n; i++) {
ll cur = i < n ? h[i] : 0; // a 0 at the end empties the stack
while (!st.empty() && h[st.back()] >= cur) {
ll height = h[st.back()];
st.pop_back();
int left = st.empty() ? -1 : st.back(); // the bar spans left+1 .. i−1
best = max(best, height * (i - left - 1));
}
st.push_back(i);
}
cout << best << "\n";
}
6
2 1 5 6 2 3
10
3. Count every window with max − min ≤ d. In the R2 loop, after shrinking, every window ending at r and starting at l..r is calm: add r − l + 1 to a long long total.
Hint
Replace best = max(best, r - l + 1) with total += r - l + 1. The answer for n = 10^6 can reach about 5·10^11.
4. Sliding-window maximum of size k. One falling deque of indices: push r, drop the front if it's ≤ r − k, and print a[front] once r ≥ k − 1.
Hint
It's the mx deque of R2 with a fixed window: if (mx.front() <= r - k) mx.pop_front();
Quick quiz
a = 2 5 3 4 1
// for each i: the nearest value to the left
// that is strictly smaller (- if none)
A) - 2 2 3 - · B) - 2 5 3 - · C) - 2 2 3 1 · D) 2 5 3 4 -
Answer
A. 5 sees 2; 3 pops 5 and sees 2; 4 sees 3; 1 pops everything, so none.
Interview questions
- What is a monotonic stack? A stack of indices whose values stay increasing (or decreasing); each new element pops the ones it dominates.
- Why is it O(n) with a while loop inside? Every index is pushed once and popped at most once, so all pops together are at most n.
- What does contribution counting mean? Instead of computing something for every subarray, count how many subarrays each element affects and add element × count.
- How do you handle equal values in the sum of minimums? Make the comparison strict on one side and non-strict on the other, so every subarray has exactly one owner.
- Monotonic stack vs deque? A deque also drops elements from its front when they leave a sliding window.
- Why store indices instead of values? To know when an element has left the window, and to keep equal values apart.
- How do you spot an infinite loop in a contest? A TLE on a tiny input (the sample) is almost never slowness.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Monotonic stack | A stack whose values stay sorted from bottom to top | nearest colder day |
| Monotonic deque | A monotonic stack that can also drop its oldest end | window max and min |
| Deque | Double-ended queue: push and pop at both ends | deque<int> |
| Nearest smaller element | The closest index to one side with a smaller value | L[i], R[i] |
| Contribution counting | Sum element × (number of subarrays it affects) | a[i]·(i − L)·(R − i) |
| Subarray / period | A contiguous block a[l..r] | days 2..4 |
| Tie-breaking | A rule that gives equal values exactly one owner | >= left, > right |
| Amortised analysis | Total cost over all steps, not per step | n pushes, ≤ n pops |
| Two pointers | Two indices that only move forward over the array | l and r |
| Sliding window | The current range l..r of two pointers | the calm window |
| Expired index | An index that has left the window (< l) | pop the front |
| Dominated element | One that can never be the answer again | a pricier shop behind a cheaper one |
| Infinite loop | A loop whose condition never becomes false | TLE on the sample |
| Overflow | A value too big for its type | use long long |
| Stress test | Fast vs brute force on many small random inputs | mismatch on test 3: 3 3 2 |
| String hashing | Fingerprints for substrings | next episode |
Summary
- Sum over all subarrays? Count each element's contribution; nearest smaller indices come from a monotonic stack in O(n).
- With equal values, compare strictly on one side and non-strictly on the other, or ties are counted twice. The sample may not show it: stress test.
- Moving windows: two pointers + two monotonic deques of indices, dropping expired fronts. O(n).
- A TLE on a tiny input means an infinite loop.
Solutions in C++, Java and Python
Problem R1 · Cold Streaks
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll fast(const vector<ll>& a) {
int n = a.size();
vector<int> L(n), R(n), st;
for (int i = 0; i < n; i++) { // previous strictly colder day
while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
L[i] = st.empty() ? -1 : st.back();
st.push_back(i);
}
st.clear();
for (int i = n - 1; i >= 0; i--) { // next colder-or-equal day
while (!st.empty() && a[st.back()] > a[i]) st.pop_back();
R[i] = st.empty() ? n : st.back();
st.push_back(i);
}
ll total = 0;
for (int i = 0; i < n; i++) total += a[i] * (i - L[i]) * (R[i] - i);
return total;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> a(n);
for (auto& x : a) cin >> x;
cout << fast(a) << "\n";
}
Java (checked on the samples and 10 random tests against the C++ brute force)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
int n = nextInt(in);
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = nextInt(in);
int[] L = new int[n], R = new int[n], st = new int[n];
int top = 0;
for (int i = 0; i < n; i++) { // previous strictly colder day
while (top > 0 && a[st[top - 1]] >= a[i]) top--;
L[i] = top == 0 ? -1 : st[top - 1];
st[top++] = i;
}
top = 0;
for (int i = n - 1; i >= 0; i--) { // next colder-or-equal day
while (top > 0 && a[st[top - 1]] > a[i]) top--;
R[i] = top == 0 ? n : st[top - 1];
st[top++] = i;
}
long total = 0;
for (int i = 0; i < n; i++) total += a[i] * (i - L[i]) * (R[i] - i);
System.out.println(total);
}
static int nextInt(DataInputStream in) throws IOException {
int r = 0, b = in.read();
while (b < '0') b = in.read();
while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
return r;
}
}
Python (Python ints never overflow)
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); a = list(map(int, data[1:1 + n]))
L, R, st = [-1] * n, [n] * n, []
for i in range(n): # previous strictly colder day
while st and a[st[-1]] >= a[i]: st.pop()
L[i] = st[-1] if st else -1
st.append(i)
st = []
for i in range(n - 1, -1, -1): # next colder-or-equal day
while st and a[st[-1]] > a[i]: st.pop()
R[i] = st[-1] if st else n
st.append(i)
print(sum(a[i] * (i - L[i]) * (R[i] - i) for i in range(n)))
main()
Problem R2 · Calm Window
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int fast(const vector<ll>& a, ll d) {
int n = a.size(), best = 0, l = 0;
deque<int> mx, mn; // indices: values falling / rising
for (int r = 0; r < n; r++) {
while (!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
while (!mn.empty() && a[mn.back()] >= a[r]) mn.pop_back();
mx.push_back(r), mn.push_back(r);
while (a[mx.front()] - a[mn.front()] > d) { // too hot: shrink
l++;
if (mx.front() < l) mx.pop_front(); // drop days that left
if (mn.front() < l) mn.pop_front();
}
best = max(best, r - l + 1);
}
return best;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll d;
cin >> n >> d;
vector<ll> a(n);
for (auto& x : a) cin >> x;
cout << fast(a, d) << "\n";
}
Java
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
int n = (int) nextLong(in);
long d = nextLong(in);
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = nextLong(in);
int[] mx = new int[n], mn = new int[n]; // deques as arrays: [head, tail)
int mxH = 0, mxT = 0, mnH = 0, mnT = 0, l = 0, best = 0;
for (int r = 0; r < n; r++) {
while (mxT > mxH && a[mx[mxT - 1]] <= a[r]) mxT--;
while (mnT > mnH && a[mn[mnT - 1]] >= a[r]) mnT--;
mx[mxT++] = r; mn[mnT++] = r;
while (a[mx[mxH]] - a[mn[mnH]] > d) { // too hot: shrink
l++;
if (mx[mxH] < l) mxH++; // drop days that left
if (mn[mnH] < l) mnH++;
}
best = Math.max(best, r - l + 1);
}
System.out.println(best);
}
static long nextLong(DataInputStream in) throws IOException {
long r = 0; int b = in.read();
while (b < '0') b = in.read();
while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
return r;
}
}
Python
import sys
from collections import deque
def main():
data = sys.stdin.buffer.read().split()
n, d = int(data[0]), int(data[1]); a = list(map(int, data[2:2 + n]))
mx, mn = deque(), deque() # indices: values falling / rising
l = best = 0
for r in range(n):
while mx and a[mx[-1]] <= a[r]: mx.pop()
while mn and a[mn[-1]] >= a[r]: mn.pop()
mx.append(r); mn.append(r)
while a[mx[0]] - a[mn[0]] > d: # too hot: shrink
l += 1
if mx[0] < l: mx.popleft() # drop days that left
if mn[0] < l: mn.popleft()
best = max(best, r - l + 1)
print(best)
main()