These are the notes for C++ episode 39. Code that gives the right answer can still fail because it's too slow. We meet the online judge and its time limit, learn to estimate steps from the constraints, and invent four patterns contest coders use every day: prefix sums, fast I/O (the contest template), two pointers and the sliding window. Every program was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13.3, the SyntaxPilot compiler's command) and run; outputs are copied from those runs. The compiler stops a program after 8 seconds and reports Time Limit Exceeded. Timings in milliseconds change from machine to machine; the comparisons don't.
The problem: 200,000 questions in one second
Ravi has kept the sales of 200,000 days. His accountant has 200,000 questions, all of one kind: what were the total sales from day l to day r? She wants every answer within one second. That's exactly what a contest problem looks like:
Input: n (days), q (questions), the n sales, then q lines "l r"
Output: for each question, the sum of sales[l..r]
Limits: 1 ≤ n, q ≤ 200,000 Time limit: 1 second
How a contest judge works
You submit your code; the judge compiles it, runs it on secret tests, and gives a verdict:
| Verdict | Meaning |
|---|---|
| Accepted (AC) | right answers, within the time and memory limits |
| Wrong Answer (WA) | at least one output is wrong |
| Time Limit Exceeded (TLE) | too slow on at least one test |
| Runtime Error (RE) | a crash: segmentation fault, uncaught exception, ... |
| Memory Limit Exceeded (MLE) | used too much memory |
| Compilation Error (CE) | it didn't compile |
Rule of thumb: a computer does about 10⁸ simple steps per second. So read the constraints first and pick an algorithm that fits:
| n up to | Fastest that fits in ~1 s |
|---|---|
| 10 | O(n!) |
| 20 | O(2ⁿ) |
| 500 | O(n³) |
| 5,000 | O(n²) |
| 10⁶ | O(n log n) or O(n) |
| 10¹⁸ | O(log n) or O(1) |
Here, re-adding the days for each question is up to n × q = 4 × 10¹⁰ steps, about 400 seconds. But n + q = 4 × 10⁵ steps is instant.
Pattern 1: prefix sums
The obvious way, and why it fails
Made-up sales ((i * 37) % 100) so the program needs no input; each question loops from day l to day r. A checksum adds up all the answers so the two methods can be compared:
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n = 200000, q = 200000; // the problem's limits
vector<long long> sales(n);
for (int i = 0; i < n; i++) sales[i] = (i * 37) % 100; // made-up sales
long long check = 0;
for (int k = 0; k < q; k++) {
int l = k % 1000, r = n - 1 - k % 1000; // question: days l to r
long long sum = 0;
for (int d = l; d <= r; d++) sum += sales[d]; // add every day
check += sum;
}
cout << "Checksum: " << check << endl;
return 0;
}
Output:
Time Limit Exceeded (stopped after 8 seconds)
Every question re-adds almost the same 200,000 days: the same work, repeated q times. (The same disease as plain recursion in episode 38.)
The fix: a running total, like a bank passbook
A passbook keeps a balance column: the total so far after every line. To know what came in between two dates, take the balance at the end minus the balance at the start. In C++, pre[i] = the total of the first i days (a prefix sum):
sales: 120 80 150 90 200 60 110
pre: 0 120 200 350 440 640 700 810
^ pre[0] = 0 (no days)
sum of days l..r = pre[r + 1] - pre[l]
days 2..4 = pre[5] - pre[2] = 640 - 200 = 440 (150 + 90 + 200)
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<long long> sales = {120, 80, 150, 90, 200, 60, 110};
int n = sales.size();
vector<long long> pre(n + 1, 0); // pre[i] = first i days
for (int i = 0; i < n; i++)
pre[i + 1] = pre[i] + sales[i]; // running total
cout << "pre:";
for (long long p : pre) cout << " " << p;
cout << endl;
int l = 2, r = 4; // days 2 to 4
cout << "Days 2 to 4: " << pre[r + 1] - pre[l] << endl;
return 0;
}
Output:
pre: 0 120 200 350 440 640 700 810
Days 2 to 4: 440
The extra 0 at the front means a range starting at day 0 needs no special case.
Now the real test: build pre once in O(n), answer each question in O(1):
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n = 200000, q = 200000;
vector<long long> sales(n), pre(n + 1, 0);
for (int i = 0; i < n; i++) sales[i] = (i * 37) % 100;
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + sales[i]; // once: O(n)
long long check = 0;
for (int k = 0; k < q; k++) {
int l = k % 1000, r = n - 1 - k % 1000;
check += pre[r + 1] - pre[l]; // each question: O(1)
}
cout << "Checksum: " << check << endl;
return 0;
}
Output:
Checksum: 1970109900000
Same checksum as the naive method would give, in milliseconds: O(n + q) in total.
Pattern 2: fast I/O
endl vs '\n'
endl means a new line and flush: the waiting text is sent out right now. '\n' just adds a new line; the text waits in a buffer** and goes out in big batches (one truck for many parcels instead of one truck per parcel). We write a million numbers to a file (like a judge reading your output) both ways and time them with <chrono>:
#include <iostream>
#include <fstream>
#include <chrono>
using namespace std;
using namespace chrono;
int main() {
ofstream out("answers.txt"); // like a judge's output file
auto t0 = steady_clock::now();
for (int i = 0; i < 1000000; i++) out << i << endl; // newline + flush
auto t1 = steady_clock::now();
for (int i = 0; i < 1000000; i++) out << i << '\n'; // just a newline
auto t2 = steady_clock::now();
auto ms = [](auto d) { return duration_cast<milliseconds>(d).count(); };
cout << "endl: " << ms(t1 - t0) << " ms" << endl;
cout << "'\\n': " << ms(t2 - t1) << " ms" << endl;
return 0;
}
Output:
endl: 403 ms
'\n': 41 ms
About 10 × slower with endl for exactly the same text. In loops, always use '\n'.
The contest template
#include <bits/stdc++.h> // every standard header at once (a g++ shortcut)
using namespace std;
using ll = long long; // a short name for big numbers
int main() {
ios::sync_with_stdio(false); // cin/cout stop syncing with C's scanf/printf
cin.tie(nullptr); // cin stops flushing cout before every read
// ... solution ...
}
bits/stdc++.his a g++-only header that includes the whole standard library. Fine for contests (it compiles a bit slower); in real projects include only what you use.ios::sync_with_stdio(false): by default C++ streams stay in step with C'sstdioso you can mixcinandscanf. Turning that off letscin/coutuse their own fast buffers. After it, don't mixcin/coutwithscanf/printf.cin.tie(nullptr): by defaultcinflushescoutbefore every read (so prompts appear). In a contest nobody reads prompts, so untie them.- On big inputs these two lines often make reading several times faster.
The template, run with input:
#include <bits/stdc++.h> // every standard header at once
using namespace std;
using ll = long long; // big sums by default
int main() {
ios::sync_with_stdio(false); // stop syncing with C's scanf/printf
cin.tie(nullptr); // don't flush cout before each cin
int n;
cin >> n;
ll total = 0;
for (int i = 0; i < n; i++) {
ll x;
cin >> x;
total += x;
}
cout << total << '\n';
return 0;
}
Input:
5
3 1 4 1 5
Output:
14
Pattern 3: two pointers
The problem
500,000 bills, sorted from smallest to biggest. A customer paid exactly x for two bills. Which two? The obvious double loop tries every pair:
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n = 500000;
vector<long long> bill(n);
for (int i = 0; i < n; i++) bill[i] = 2 * i; // sorted: 0, 2, 4, ...
long long x = 4LL * n - 6; // the total we need
for (int i = 0; i < n; i++) // try every pair
for (int j = i + 1; j < n; j++)
if (bill[i] + bill[j] == x) {
cout << "Bills " << i << " and " << j << endl;
return 0;
}
cout << "No pair" << endl;
return 0;
}
Output:
Time Limit Exceeded (stopped after 8 seconds)
About n²/2 = 1.25 × 10¹¹ pairs, and it never used the fact that the bills are sorted.
The fix: walk in from both ends
Two friends stand at the two ends of a queue sorted by height. i starts at the smallest bill, j at the biggest:
bill[i] + bill[j] == x: found.- sum too small: even the biggest bill can't help
bill[i], so drop it:i++. - sum too big: even the smallest bill is too much with
bill[j], so drop it:j--.
Every step throws one bill away, so it ends after at most n steps: O(n).
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n = 500000;
vector<long long> bill(n);
for (int i = 0; i < n; i++) bill[i] = 2 * i;
long long x = 4LL * n - 6;
int i = 0, j = n - 1, steps = 0; // smallest and biggest bill
while (i < j) {
steps++;
long long s = bill[i] + bill[j];
if (s == x) break;
if (s < x) i++; // too small: a bigger left bill
else j--; // too big: a smaller right bill
}
if (i < j) cout << "Bills " << i << " and " << j << endl;
else cout << "No pair" << endl;
cout << "Steps: " << steps << endl;
return 0;
}
Output:
Bills 499998 and 499999
Steps: 499999
This only works because the data is sorted. On unsorted data, sort first (O(n log n)), or use an unordered_set of seen values (O(n) on average).
Pattern 4: sliding window
Ravi's best week: the 7 days in a row with the highest total. Re-adding every week is O(n × k). Instead, add the first week once, then slide forward a day at a time: the new day comes in, the oldest drops out. Two operations per day, whatever k is: O(n).
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<long long> sales = {120, 80, 150, 90, 200, 60, 110,
170, 40, 130, 210, 90, 60, 180};
int n = sales.size(), k = 7; // best run of 7 days
long long win = 0;
for (int i = 0; i < k; i++) win += sales[i]; // the first week
long long best = win; int start = 0;
for (int i = k; i < n; i++) {
win += sales[i] - sales[i - k]; // add the new day, drop the oldest
if (win > best) { best = win; start = i - k + 1; }
}
cout << "Best week: days " << start << " to " << start + k - 1
<< ", total " << best << endl;
return 0;
}
Output:
Best week: days 4 to 10, total 920
Check: days 4 to 10 are 200 + 60 + 110 + 170 + 40 + 130 + 210 = 920.
A window of variable size (grow on the right, shrink on the left) solves "shortest run with total ≥ X" (practice 3 below): it's two pointers moving in the same direction.
Cheat sheet
| Situation | Pattern | Time |
|---|---|---|
| Many range-sum queries on fixed data | prefix sums: pre[r + 1] - pre[l] |
O(n) build, O(1) per query |
| Many "add v to every element in l..r" updates | difference array (mini project) | O(1) per update, O(n) at the end |
| Lots of input | ios::sync_with_stdio(false); cin.tie(nullptr); |
several × faster reading |
| Lots of output | '\n', never endl in loops |
about 10 × faster here |
| A pair with a given sum in sorted data | two pointers from both ends | O(n) |
| Best/shortest run of consecutive elements | sliding window | O(n) |
| Any sum of many values | long long |
Common mistakes
| Mistake | What you see | Fix |
|---|---|---|
Sums in an int |
three sales of 10⁹ print Total: -1294967296 (an int holds up to 2,147,483,647) |
long long (ll) for every sum |
pre[r] - pre[l] |
Days 2 to 4: 240 instead of 440 (day r is missed) |
pre[r + 1] - pre[l] with pre[0] = 0 |
endl in a big output loop |
about 10 × slower: can turn Accepted into Time Limit Exceeded | '\n' |
| Two pointers on unsorted data | No pair for {50, 10, 40, 20} and x = 90, but 50 + 40 = 90 |
sort first |
Mixing scanf and cin after sync_with_stdio(false) |
input read out of order | use only one of them |
| An O(n²) idea with n = 200,000 | Time Limit Exceeded | read the limits first: 4 × 10¹⁰ steps is too many |
Run for real:
#include <iostream>
using namespace std;
int main() {
int sales[3] = {1000000000, 1000000000, 1000000000};
int total = 0; // int: up to about 2.1 billion
for (int s : sales) total += s;
cout << "Total: " << total << endl;
return 0;
}
Output:
Total: -1294967296
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> bill = {50, 10, 40, 20}; // NOT sorted
int x = 90, i = 0, j = bill.size() - 1;
while (i < j) {
int s = bill[i] + bill[j];
if (s == x) break;
if (s < x) i++; else j--;
}
if (i < j) cout << bill[i] << " + " << bill[j] << endl;
else cout << "No pair" << endl;
return 0;
}
Output:
No pair
The off-by-one version (pre[r] - pre[l]):
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<long long> sales = {120, 80, 150, 90, 200, 60, 110};
int n = sales.size();
vector<long long> pre(n + 1, 0); // pre[i] = first i days
for (int i = 0; i < n; i++)
pre[i + 1] = pre[i] + sales[i]; // running total
cout << "pre:";
for (long long p : pre) cout << " " << p;
cout << endl;
int l = 2, r = 4; // days 2 to 4
cout << "Days 2 to 4: " << pre[r] - pre[l] << endl;
return 0;
}
Output:
pre: 0 120 200 350 440 640 700 810
Days 2 to 4: 240
Mini project: price offers with a difference array
Ravi runs q offers; each adds add rupees to the price on every day from l to r. What is the extra on each day? Adding to every day of every offer is O(n × q). Instead, mark only where an offer starts (diff[l] += add) and where it stops (diff[r + 1] -= add), then a prefix sum of diff gives each day's total: O(n + q). This is a difference array, the reverse of a prefix sum.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q; // n days, q offers
vector<long long> diff(n + 1, 0);
for (int k = 0; k < q; k++) {
int l, r; long long add;
cin >> l >> r >> add; // add rupees to every day l..r
diff[l] += add; // starts here
diff[r + 1] -= add; // stops after r
}
long long running = 0;
for (int i = 0; i < n; i++) {
running += diff[i]; // a prefix sum of the differences
cout << running << (i + 1 < n ? ' ' : '\n');
}
return 0;
}
Input:
7 3
0 3 10
2 6 5
4 4 20
Output:
10 10 15 15 25 5 5
Check: day 0 gets only offer 1 (10); day 2 gets offers 1 and 2 (15); day 4 gets offers 2 and 3 (25); day 5 only offer 2 (5).
Practice
- Count the days between l and r with sales over 100 (prefix counts).
- Find a pair with sum x in an unsorted list.
- Find the shortest run of consecutive days with a total of at least 500.
- Write your own template file and start every solution from it.
Solutions
Exercise 1: a prefix sum of 1s and 0s counts in O(1) per question.
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> sales = {120, 80, 150, 90, 200, 60, 110};
int n = sales.size();
vector<int> cnt(n + 1, 0); // cnt[i] = good days among the first i
for (int i = 0; i < n; i++)
cnt[i + 1] = cnt[i] + (sales[i] > 100 ? 1 : 0);
int l = 1, r = 5;
cout << "Days " << l << " to " << r << " over 100: " << cnt[r + 1] - cnt[l] << '\n';
return 0;
}
Output:
Days 1 to 5 over 100: 2
Days 1 to 5 are 80, 150, 90, 200, 60: two of them are over 100.
Exercise 2: sort, then two pointers.
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> bill = {50, 10, 40, 20};
int x = 90;
sort(bill.begin(), bill.end()); // 10 20 40 50
int i = 0, j = bill.size() - 1;
while (i < j) {
int s = bill[i] + bill[j];
if (s == x) break;
if (s < x) i++; else j--;
}
if (i < j) cout << bill[i] << " + " << bill[j] << " = " << x << '\n';
else cout << "No pair" << '\n';
return 0;
}
Output:
40 + 50 = 90
Exercise 3: a variable-size sliding window. Grow it to the right; while its total is enough, record its length and shrink it from the left. Each day enters and leaves the window once: O(n).
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> sales = {120, 80, 150, 90, 200, 60, 110, 170, 40, 130, 210, 90, 60, 180};
int n = sales.size(), need = 500;
int best = INT_MAX, bestL = -1;
long long win = 0;
int l = 0;
for (int r = 0; r < n; r++) { // grow the window to the right
win += sales[r];
while (win >= need) { // shrink from the left while it's enough
if (r - l + 1 < best) { best = r - l + 1; bestL = l; }
win -= sales[l];
l++;
}
}
cout << "Shortest run with total >= " << need << ": " << best
<< " days, from day " << bestL << '\n';
return 0;
}
Output:
Shortest run with total >= 500: 4 days, from day 1
Days 1 to 4: 80 + 150 + 90 + 200 = 520.
Exercise 4: the template above, saved as template.cpp.
Quick quiz
vector<int> a = {3, 1, 4, 1, 5, 9};
vector<int> pre(7, 0);
for (int i = 0; i < 6; i++)
pre[i + 1] = pre[i] + a[i];
cout << pre[5] - pre[2];
Answer
10. pre[5] - pre[2] is a[2] + a[3] + a[4] = 4 + 1 + 5. The full program, run:
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> a = {3, 1, 4, 1, 5, 9};
vector<int> pre(7, 0);
for (int i = 0; i < 6; i++)
pre[i + 1] = pre[i] + a[i];
cout << pre[5] - pre[2] << endl;
return 0;
}
Output:
10
Interview questions
- How do you answer many range-sum queries quickly? Prefix sums: O(n) preprocessing, O(1) per query with
pre[r + 1] - pre[l]. - What's the difference between
endland'\n'? Both end the line;endlalso flushes the stream, which is slow in loops. - What do
ios::sync_with_stdio(false)andcin.tie(nullptr)do? Stop syncing C++ streams with C stdio, and stopcinflushingcoutbefore each read; both speed up I/O. - Why does two pointers need sorted data? Moving
iright must make the sum bigger and movingjleft smaller; only sorted order guarantees that, which is what makes discarding a bill safe. - Two pointers vs a hash set for pair sum? Two pointers: O(n) on sorted data, O(1) extra memory. Hash set: O(n) average on unsorted data, O(n) memory.
- What is a sliding window? A range [l, r] that moves forward, updated in O(1) per step (add the new element, remove the old), instead of recomputing every range.
- How many operations fit in one second? About 10⁸ simple operations; use the constraints to choose the complexity.
- Range updates, then the final array? A difference array:
diff[l] += v; diff[r + 1] -= v;, then a prefix sum.
Glossary
| Term | Meaning, with an example |
|---|---|
| competitive programming | Solving well-defined problems against a judge, fast and correctly (Codeforces, AtCoder, CodeChef). |
| online judge | The system that runs your code on secret tests and gives a verdict. |
| verdict | The judge's result: Accepted, Wrong Answer, Time Limit Exceeded, Runtime Error... |
| time limit | The longest your program may run, often 1-2 seconds. |
| Time Limit Exceeded (TLE) | Too slow: the judge stopped the program. |
| constraints | The limits on the input, like 1 ≤ n ≤ 200,000; they tell you the complexity you need. |
| query | One question to answer, like "sum of days l..r". |
| checksum | A number combining many results, used to compare outputs quickly. |
| prefix sum | pre[i] = the total of the first i elements: a running total. |
| range sum | The sum of elements l..r: pre[r + 1] - pre[l]. |
| difference array | Marks where additions start and stop; its prefix sum gives the final values. |
| flush | Send the buffered output out now; endl flushes, '\n' doesn't. |
| buffer | Memory where output waits, so it can be sent in big batches. |
| fast I/O | ios::sync_with_stdio(false); cin.tie(nullptr); plus '\n'. |
bits/stdc++.h |
A g++ header that includes the entire standard library. |
using ll = long long; |
A type alias: ll is a shorter name for long long. |
<chrono> / steady_clock |
The standard library's clocks, for measuring elapsed time. |
| two pointers | Two indexes moving through the data (from both ends, or in the same direction) to avoid checking every pair. |
| sliding window | A range of consecutive elements moved forward one step at a time. |
| integer overflow | A sum too big for int wraps around to a negative number. |
| off-by-one error | Being wrong by one index: pre[r] instead of pre[r + 1]. |
Summary
- Read the constraints first; about 10⁸ simple steps per second.
- Prefix sums answer range sums in O(1) after O(n) preparation; a difference array does range updates.
- Fast I/O:
ios::sync_with_stdio(false); cin.tie(nullptr);and'\n'instead ofendl. Uselong longfor sums. - Two pointers find pairs in sorted data in O(n); a sliding window finds the best run of k in a row in O(n).
- Next episode: the capstone project, a real billing system using everything from the course.