ii. Fast I/O and Constant Factor

Use this when the complexity is right but the time limit isn’t. Fix things in this order: complexity, then memory access, then I/O, then micro-optimisation. A removed $\log$ beats any amount of tuning. If you’re within about 2x of the limit, the techniques below almost always close the gap.

I/O

Step	Gain	Note
cin.tie(nullptr)->sync_with_stdio(false)	3-10x	don’t mix with scanf/printf afterwards
'\n' instead of endl	huge on big output	endl flushes; $10^6$ flushes cost about a second
build output in one string, print once	1.5-2x	for $10^6$+ lines
fread + hand parser	2-5x over unsynced cin	only for $\gtrsim 5\cdot 10^6$ numbers

Rough times for reading $10^7$ integers: synced cin about 4 s, unsynced about 0.9 s, scanf about 1.2 s, fread parser about 0.15 s.

static char buf[1 << 25];
size_t bl = 0, bp = 0;
inline int gc() {
    if (bp == bl) { bl = fread(buf, 1, sizeof buf, stdin); bp = 0; if (!bl) return -1; }
    return buf[bp++];
}
inline ll readInt() {
    int c = gc(); while (c != '-' && (c < '0' || c > '9')) c = gc();
    bool neg = c == '-'; if (neg) c = gc();
    ll x = 0; for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
    return neg ? -x : x;
}
static char obuf[1 << 25]; size_t op = 0;
inline void writeInt(ll x, char end = '\n') {
    if (x < 0) obuf[op++] = '-', x = -x;
    char t[20]; int n = 0;
    do t[n++] = '0' + x % 10, x /= 10; while (x);
    while (n) obuf[op++] = t[--n];
    obuf[op++] = end;
}
// at exit: fwrite(obuf, 1, op, stdout);

Line input: after cin >> n, call cin.ignore() (or cin >> ws) before getline, otherwise getline returns the empty rest of the line. Read until EOF with while (cin >> x).

__int128 streams:

istream& operator>>(istream& is, i128& x) { string s; is >> s; x = 0; bool neg = s[0] == '-';
    for (size_t i = neg; i < s.size(); i++) x = x * 10 + (s[i] - '0'); if (neg) x = -x; return is; }
ostream& operator<<(ostream& os, i128 x) { if (x < 0) os << '-', x = -x; string s;
    do s += char('0' + x % 10), x /= 10; while (x); return os << string(s.rbegin(), s.rend()); }

File I/O for USACO and old judges: freopen("name.in", "r", stdin); freopen("name.out", "w", stdout);, guarded by #ifndef LOCAL.

Judges that run your code on your own machine (Hacker Cup) allow solving test cases on several threads: read everything, solve with a std::thread pool pulling indices from an atomic<int>, then print in order. Never do this on Codeforces. solve() must not touch shared mutable globals when run this way — give each test its own data; only the sequential read phase may share state.

Code Jam / Kick Start / Hacker Cup also want a specific multi-test output format: print "Case #" << t << ": " before every answer, t 1-indexed.

putchar_unlocked/getchar_unlocked skip the per-call mutex that putchar/getchar acquire — safe in a single-threaded program, and roughly 2x faster than the locked versions, though fread/fwrite buffering above already captures most of that gain.

Memory access is usually the biggest win

Change	Effect
innermost loop over the last index	up to 10x on $5000\times 5000$
flatten vector<vector<T>> into one array, index i * m + j	removes a pointer chase per access
i, k, j order in matrix multiply	3-5x, and lets GCC vectorise
struct of arrays instead of array of structs when only one field is hot	fewer cache lines
renumber vertices in BFS/DFS order (tree problems)	adjacency becomes local
int instead of ll where the range allows	half the bandwidth
CSR graph (head, to) instead of vector<vector<int>>	1.5-3x for graph traversals with $10^6$ edges

Cache sizes matter: L1 is about 32 KB, L2 about 256 KB-1 MB, L3 several MB. A random access into a 400 MB table is a cache miss of about 100 ns, so $10^8$ random accesses is 10 s, not 0.1 s.

Eytzinger layout for repeated binary search

Store a static sorted array in BFS order of the implicit complete binary search tree (node $k$ has children $2k$, $2k+1$): the first few levels then share cache lines, and the descent is branch-free.

struct Eytzinger {                                           // cache-friendly lower_bound on a static sorted array
    vector<int> t; int n;
    Eytzinger(const vector<int>& sorted) : t(sz(sorted) + 1), n(sz(sorted)) { int i = 0; build(sorted, i, 1); }
    void build(const vector<int>& a, int& i, int k) { if (k <= n) { build(a, i, 2 * k); t[k] = a[i++]; build(a, i, 2 * k + 1); } }
    int lowerBound(int x) const {                            // smallest element >= x, or INT_MAX
        int k = 1;
        while (k <= n) k = 2 * k + (t[k] < x);
        k >>= __builtin_ffs(~k);
        return k ? t[k] : INT_MAX;
    }
};

Proof: the descent finds the lower bound

The in-order traversal of the implicit tree visits $t[\mathrm{1..}n]$ in sorted order (that is how build fills it). The descent goes right exactly when $t[k]<x$, so the path ends below a leaf, and the answer is the last node where the descent went left. Each right step appends a $1$ bit to $k$ and each left step a $0$ bit, so the last left turn is undone by shifting out the trailing ones plus one more bit — exactly k >>= __builtin_ffs(~k). If the descent never went left, $k$ becomes $0$ and no element is $\ge x$.

Tested against std::lower_bound on random sorted arrays and random queries, including queries below the minimum and above the maximum.

Worth it only for many repeated queries on the same static array (rebuilding costs as much as one sort); for a handful of queries, plain lower_bound is simpler and the asymptotic cost is identical either way.

Expensive operations

Slow	Faster
% in the inner loop	if (x >= M) x -= M; after an addition (values stay below $2M$)
a * b % M many times	Barrett/Montgomery reduction (fast modmul), or accumulate in u64 and reduce rarely: $8M^2<2^{64}$ for $M<2^{30}$ lets you add 8 products before one %
division by a runtime constant	precomputed reciprocal; the compiler does it for compile-time constants, so make MOD constexpr
map/set	sorted vector + lower_bound, or arrays after compression
unordered_map	gp_hash_table, or an array if keys are bounded
vector<bool> in a hot loop	vector<char> or bitset
std::function	template lambda (auto&&)
endl, pow, log, sqrt on integers	'\n', loops, __lg, integer sqrt
repeated push_back	reserve first
deque as a stack/queue	vector + head index

Branch prediction: sorted data makes if (a[i] > x) predictable, and that alone can be a 3-5x difference. Branchless forms (x += (a[i] > t) * a[i]) help when the data is random.

Pragmas

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

These give 2-4x on tight numeric loops, bitset work and __builtin_popcount (a single instruction with popcnt). Put them before the includes. They are fine on Codeforces and AtCoder; on an unknown judge with an old CPU, avx2 can cause an illegal-instruction RE. O3 occasionally slows code down, so measure.

What GCC auto-vectorises: simple loops over contiguous arrays with no aliasing and no data-dependent control flow. An $O(n^2)$ loop of a[i] = min(a[i], b[i] + c) over int with AVX2 runs about $8$ elements per instruction, so $n=10^5$ ($10^{10}/8\approx 10^9$ simple ops) can pass in 2-3 s. That is the ”$O(n^2)$ with pragmas” trick on Codeforces.

Bitset: divide by 64

When an inner loop does the same boolean operation over many independent bits, pack them into words: subset sum dp |= dp << w, transitive closure, dense matching, LCS. $10^{10}$ becomes $1.6\cdot 10^8$. See Bitset.

Allocation

Node-based structures (treaps, tries, persistent segment trees, map<int, vector<int>>) spend much of their time in new. Options:

• Preallocate node pools as global arrays and use indices instead of pointers. Indices are half the size of pointers and cache better.
• Bump allocator: override global new to bump a pointer into a static buffer, with delete a no-op. Fast, but memory is never freed, so a growing vector leaks its old buffers. Use it with reserve or only for node containers.

static char mem[450 << 20]; size_t used = 0;
void* operator new(size_t s) { s = (s + 15) & ~size_t(15); void* p = mem + used; used += s; return p; }
void operator delete(void*) noexcept {}
void operator delete(void*, size_t) noexcept {}

Algorithmic constant factors

Instead of	Use
recursive segment tree for sums	Fenwick tree (about 3x faster) or bottom-up segment tree (about 2x)
set for sliding-window min	monotonic deque
sort for the $k$-th element	nth_element
heap Dijkstra on a dense graph	$O(V^2)$ array Dijkstra
$n$ separate powmod inverses	batch inverse: prefix products, one inverse, walk back; or, for every inverse $\mathrm{1..}n$ specifically, the $O(n)$ sieve below
rebuilding a structure per query	reuse with rollback
long double everywhere	double where precision allows (roughly 2x faster)

vector<int> inversesUpTo(int n, int m) {                     // inv[i] = i^{-1} mod m (m prime, n < m), O(n)
    vector<int> inv(n + 1); inv[1] = 1;
    for (int i = 2; i <= n; i++) inv[i] = m - (long long)(m / i) * inv[m % i] % m;
    return inv;
}

Proof: the linear inverse recurrence

Write $m=qi+r$ with $q=\lfloor m/i\rfloor$, $r=m\mathrm{mod}i<i$. Then $qi+r\equiv 0(\mathrm{mod}m)$, so $i\equiv -r{q}^{-1}$ and $i^{-1}\equiv -q{r}^{-1}(\mathrm{mod}m)$. Since $r<i$, $r^{-1}$ is already computed earlier in the loop ($r\ne 0$ because $m$ is prime and $i<m$). Tested against powmod(i, m-2, m) for every $i\le 10^5$ modulo $998244353$. $■$

Measure, don’t guess

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

Generate the true worst case (maximum $n$, adversarial structure such as a path graph, a star, all-equal values, sorted input), time it locally with -O2, and assume the judge is 1-2x slower than your machine.

Sorting queries offline so consecutive ones touch nearby data (Mo’s order, Hilbert order) is as much a cache optimisation as an algorithmic one (Mo’s Algorithm).