Constant Factor Optimization

When the complexity is right but the time limit is not.

Fast input/output

ios::sync_with_stdio(false);
cin.tie(nullptr);

Two lines, up to 10× faster on large input. Do this always.

For the extreme cases ($10^7$ numbers), hand-rolled reading:

static char buf[1 << 25];
int bufPos = 0;
int readInt() {
    while (buf[bufPos] < '0') bufPos++;
    int x = 0;
    while (buf[bufPos] >= '0') x = x * 10 + buf[bufPos++] - '0';
    return x;
}
// read the whole input once: fread(buf, 1, sizeof buf, stdin);

Also: use "\n" instead of endl (which flushes), and build the output in a single string before printing.

Cache locality — usually the biggest win

Change	Effect
Iterate the last index innermost	up to 10× on large 2D arrays
Flatten vector<vector<int>> to a 1D array	removes a pointer chase
i, k, j loop order for matrix multiply	3-5×
Structure of arrays instead of array of structures	better vectorisation
Sort data by access order	fewer cache misses
reserve() before push_back	avoids reallocation

Cache effects routinely dominate instruction count. A $5000\times 5000$ traversal in the wrong order can be ten times slower with identical asymptotics.

Compiler pragmas

#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx2,popcnt,bmi,bmi2")

Enables vectorisation and single-instruction popcount/ctz. Legitimate on Codeforces; a 2-4× speedup for tight numeric loops and bitset work. Check that the judge permits them, and that the target architecture is supported.

Avoiding expensive operations

Slow	Faster
% in the innermost loop	subtract conditionally: if (x >= M) x -= M;
Division	multiply by a precomputed reciprocal, or restructure
map / set	sorted vector + binary search
unordered_map	gp_hash_table, or a plain array if keys are bounded
vector<bool> in a hot loop	vector<char> (no bit fiddling) or bitset (bulk ops)
Recursion	an explicit stack or an iterative rewrite
pow, log, sqrt	integer alternatives, __lg, precomputed tables
Repeated push_back	reserve first
string concatenation in a loop	build once, or += into a preallocated buffer
Virtual calls / std::function	lambdas or templates

Replacing % with a conditional subtract is worth calling out: in modular DP inner loops it is often a 2× speedup, because the values never exceed $2M$.

sum += a[i];
if (sum >= MOD) sum -= MOD;                  // instead of sum %= MOD

Bitset — the $/64$ speedup

Whenever an inner loop does the same simple thing to many independent booleans, do 64 at a time:

bitset<MAXW> dp;
dp |= dp << x;                                // subset sum in O(nW/64)

Turns $O(n^2)$ into $O(n^2/64)$ — the difference between $10^{10}$ and $1.6\cdot 10^8$. See Bitset Optimization.

Memory layout

• Prefer int over long long when the range allows — half the memory, better cache use.
• Use static arrays over vector in the hottest paths (no indirection, no bounds).
• Pack structs; avoid padding waste.
• Reuse buffers across test cases rather than reallocating.

Algorithmic constant factors

Instead of	Use
Segment tree for prefix sums	Fenwick tree — 3× faster, half the code
Recursive segment tree	iterative (bottom-up) — 2× faster
set for a sliding-window min	monotonic deque
Sorting for the $k$-th element	nth_element
Dijkstra on a dense graph	the $O(V^2)$ array version
Full sort when only the top $k$ matter	partial_sort
Repeated powmod for inverses	batch inverse
Building a whole structure per query	reuse and roll back

Measure, do not guess

auto t0 = chrono::steady_clock::now();
// ... section ...
cerr << chrono::duration<double>(chrono::steady_clock::now() - t0).count() << "s\n";

The bottleneck is frequently not where it feels like it is. Time the sections before optimising any of them.

When to stop

If the complexity is right and the constant is reasonable, further micro-optimisation is usually the wrong investment — look for a better algorithm instead. A $\log$ factor removed beats any amount of loop tuning.

Conversely, if you are within 2× of the limit, the techniques above will almost always close the gap.

See also: Bitset Optimization · Debugging · Complexity Cheatsheet