Fast IO and the Contest Template

The counting idiom, recalled

Lesson 9-1 introduced freq[w]++ on a map. When w is missing, that creates the key with a value of 0 and then increments it to 1.

operator[] inserts a default-constructed value for a missing key, which is 0 for int, so the increment always has something to work on. That makes freq[w]++ a complete counting idiom in one line, and it is worth keeping in your pocket, because this unit turns everything so far into the small toolkit you carry into interviews.

Making cin fast enough for big inputs

Judge problems can feed you hundreds of thousands of numbers. Two lines at the top of main make C++ streams read them fast:

std::ios::sync_with_stdio(false);  // stop syncing with C's stdio
std::cin.tie(nullptr);             // stop flushing cout before every cin

And prefer "\n" over std::endl (lesson 1-2): endl forces a flush on every line, which is slow in a tight loop.

Two more habits

Read until the input ends. std::cin >> x evaluates to false when input runs out, so an unknown-length stream is just:

int x;
while (std::cin >> x) { /* use x */ }

You used this in lesson 9-1's word counter.

Sum in long long. An int caps near 2.1 billion (lesson 2-1). Summing 100,000 values that can each be a billion overflows int silently. long long holds about ±9.2 × 10¹⁸. In contests, when in doubt, sums and products are long long.

The standard contest opening

Fast IO, a read-until-end loop, and a 64-bit accumulator, which is the shape most competitive solutions start from.

#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    long long sum = 0;
    int count = 0;

    int x;
    while (std::cin >> x) {
        sum += x;
        count++;
    }

    std::cout << "count: " << count << "\n";
    std::cout << "sum: " << sum << "\n";
    return 0;
}

Input

1000000000 1000000000 1000000000 5

Output

count: 4
sum: 3000000005

The input is chosen to break an int accumulator. Three billion already exceeds the roughly 2.1 billion ceiling, so with int sum this program would print a wrapped, meaningless value while looking perfectly correct.

Note that x stays an int while sum is a long long. Each individual value fits comfortably, and only the running total needs the wider type, so widening the accumulator alone is the cheapest fix.

The two fast-IO lines must come before any reading happens. Calling sync_with_stdio(false) after the first extraction is undefined behavior, which is why they belong at the very top of main.

Summing three billion into an int

Adding three values of 1,000,000,000 into an int overflows its ceiling of about 2.1 billion, and signed overflow is undefined behavior.

In practice the value wraps to a wrong and often negative number, with no warning at run time and no crash to point at the line. The compiler is also entitled to assume the overflow cannot happen and optimize on that basis, so the observed behavior can change between builds.

The fix costs nothing, being a single long long on the accumulator's declaration:

long long sum = 0;
sum += 1000000000;
sum += 1000000000;
sum += 1000000000;   // 3000000000, correct

This single bug fails more interview submissions than almost any other C++ mistake, and it is worth pre-empting rather than debugging. The habit to build is to ask what the largest possible total is before writing the declaration, which is the same estimate lesson 2-1 introduced.

Tracking min, max, and sum in one pass

One loop reading an unknown number of values, maintaining three results at once.

#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    long long sum = 0;
    int mn = 0, mx = 0;
    bool first = true;

    int x;
    while (std::cin >> x) {
        sum += x;
        if (first) {
            mn = x;
            mx = x;
            first = false;
        } else {
            if (x < mn) mn = x;
            if (x > mx) mx = x;
        }
    }

    std::cout << "min: " << mn << "\n";
    std::cout << "max: " << mx << "\n";
    std::cout << "sum: " << sum << "\n";
    return 0;
}

Input

4 -2 9 4 7

Output

min: -2
max: 9
sum: 22

The first flag solves the same problem lesson 3-3 solved by reading one value before the loop. Here the count is unknown, so there is no separate read to hoist out, and the flag makes the initial values come from real data rather than from a guessed sentinel.

Initializing mn and mx to 0 without the flag would be wrong in a way this input demonstrates. The minimum would come out as -2 by luck, but a list of all-positive values would report a minimum of 0, and a list of all-negative values would report a maximum of 0.

The two comparisons can be replaced by mn = std::min(mn, x); and mx = std::max(mx, x); using lesson 9-2's helpers, which is shorter and equally clear.