C++ Language Essentials

Quick Revisit

• CORE IDEA: How you pass data (&) and what type you store it in (int vs long long) silently determines WA/TLE vs AC
• CLASSIC BUGS: pass-by-value copies on containers · int overflow at $2.1\times {10}^9$ · size_t unsigned wraparound
• PRACTICE: 1100–1400 Ladder

The C++ features every competitive programmer uses but nobody explicitly teaches: integer overflow, pass-by-reference, memory layout, undefined behavior, lambdas, and structured bindings. This file covers the language itself—the substrate on which every algorithm in this notebook runs.

Difficulty	Beginner
CF Rating	800–1300
Prerequisites	Basic C++ syntax (variables, loops, functions, if/else)

---

Contents

• Intuition
• C++ STL Reference
• Implementation
• Operations Reference
• Patterns and Tricks
• Contest Cheat Sheet
• Gotchas and Debugging
• When NOT to Use These Features
• Self-Test
• Practice Problems
• Further Reading

---

Intuition

A Bug That Costs You the Contest

You write a function to remove duplicates from a vector:

#include <bits/stdc++.h>
using namespace std;

void removeDuplicates(vector<int> v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

int main() {
    vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    removeDuplicates(a);
    cout << "Size after dedup: " << a.size() << "\n";
    // Expected: 7 (unique elements: 1,2,3,4,5,6,9)
    // Actual:   10
}

Output: Size after dedup: 10. The vector is untouched.

Why? The function signature says vector<int> v—that's pass by value. When you call removeDuplicates(a), the compiler copies all 10 elements into a fresh local vector v. The function sorts and deduplicates the copy. When removeDuplicates returns, the copy is destroyed. a never changes.

Count the damage:

• 10 integers copied into a new vector (heap allocation + copy)
• The sort and dedup work on the copy—wasted CPU
• The caller's data is unchanged—wrong answer

For a vector of ${10}^6$ elements this isn't just a logic bug—the extra copy costs ~4 MB of memory and millions of wasted operations. In a contest, this is either WA (wrong answer) or TLE (time limit exceeded), and you have no compiler error to guide you.

Now consider this related trap:

int a = 200000;
int b = a * a;  // What is b?

${200000}^2=4\times {10}^{10}$. But int maxes out at $\approx 2.1\times {10}^9$. The multiplication overflows silently—no crash, no warning, just a garbage value. Worse, signed overflow is undefined behavior in C++, so the compiler is free to do literally anything.

These two bugs—invisible copies and silent overflow—account for more WA/TLE verdicts at the 800–1300 level than any algorithmic mistake.

---

The Core Insight

C++ gives you manual control over how data moves between functions and what size integers you use. Understanding value vs. reference and int vs. long long is the difference between TLE/WA and AC.

Think of a function call like handing documents to a colleague. Pass by value hands them a photocopy—they can scribble on it freely, your original is safe, but their edits evaporate when they're done. Pass by reference hands them your original—their edits stick, but they could also accidentally spill coffee on it. const reference lets them read your original through a glass window: they see everything but can't modify it, and no copy is made.

Bjarne Stroustrup designed C++ as "C with Classes," and the explicit control over memory and copying that trips up CP beginners is the same philosophy that makes it the fastest language on every online judge. You inherit both the power and the foot-guns.

The payoff once you internalize this: every function signature becomes a performance contract. Passing a vector by value is like photocopying a textbook every time you lend it; passing by reference is just pointing a friend to the right shelf. Large containers are expensive to photocopy—small types like int and double are not. Once you see it that way, you stop writing accidental $O(n^2)$ solutions.

Here's exactly what happens under the hood when a function call copies—or doesn't—your data.

---

How Memory Moves

Pass by value vs. pass by reference

When you call f(a), what happens in memory depends on the function signature:

  Pass by VALUE: void f(vector<int> v)
  +-------------------------------+
  |  main()'s stack frame         |
  |  a: [3, 1, 4, 1, 5]  --------+---> heap block A (5 ints)
  +-------------------------------+
  |  f()'s stack frame            |
  |  v: [3, 1, 4, 1, 5]  --------+---> heap block B (5 ints) <-- COPY!
  +-------------------------------+
  Two heap blocks.  Changes to v don't touch a.


  Pass by REFERENCE: void f(vector<int>& v)
  +-------------------------------+
  |  main()'s stack frame         |
  |  a: [3, 1, 4, 1, 5]  --------+---> heap block A (5 ints)
  +-------------------------------+
  |  f()'s stack frame            |
  |  v: (alias for a)  -----------+--/
  +-------------------------------+
  One heap block.  v IS a.  Changes to v change a.


  Pass by CONST REFERENCE: void f(const vector<int>& v)
  +-------------------------------+
  |  main()'s stack frame         |
  |  a: [3, 1, 4, 1, 5]  --------+---> heap block A (5 ints)
  +-------------------------------+
  |  f()'s stack frame            |
  |  v: (read-only alias)  -------+--/
  +-------------------------------+
  One heap block.  v IS a but cannot modify it.

Lambda captures

Lambdas can "capture" variables from the surrounding scope. The capture mode determines whether the lambda gets copies or references:

  int x = 10, y = 20;

  Capture by value [=]:
  +------------------+     +------------------+
  | outer scope      |     | lambda object    |
  | x = 10           |     | x_copy = 10      |  <-- independent copy
  | y = 20           |     | y_copy = 20      |  <-- independent copy
  +------------------+     +------------------+
  Lambda modifying x_copy does NOT change outer x.

  Capture by reference [&]:
  +------------------+     +------------------+
  | outer scope      |     | lambda object    |
  | x = 10  <--------+-----+-- &x             |  <-- same variable
  | y = 20  <--------+-----+-- &y             |  <-- same variable
  +------------------+     +------------------+
  Lambda modifying x DOES change outer x.

In competitive programming, [&] is the default choice because your DFS lambda needs to write to visited, dist, parent, and so on.

Stack vs. heap memory layout

  PROCESS MEMORY MAP (simplified)
  +----------------------------------+  high addresses
  |  Stack (grows downward)          |
  |  - local variables               |
  |  - function call frames          |
  |  - default limit: 1-8 MB         |
  |           |                      |
  |           v                      |
  |                                  |
  |           ^                      |
  |           |                      |
  |  Heap (grows upward)             |
  |  - vector/string data            |
  |  - new/malloc allocations        |
  |  - limit: ~256 MB (typical ML)   |
  +----------------------------------+
  |  BSS segment                     |
  |  - global/static arrays          |
  |  - zero-initialized              |
  |  - limit: ~256 MB                |
  +----------------------------------+
  |  Text segment (your code)        |
  +----------------------------------+  low addresses

Key takeaway: int arr[1000000]; inside main() uses ~4 MB of stack (which may be all of it). The same declaration at global scope goes into BSS and is effectively unlimited. vector<int> arr(1000000); always allocates on the heap regardless of where it's declared.

---

The Rules

+--------------------------------------------------------------------+
| RULE 1: int is 32 bits, long long is 64 bits.  If intermediate     |
| products can exceed 2*10^9, use long long.                         |
+--------------------------------------------------------------------+
| RULE 2: Pass containers (vector, string, map) by const& for        |
| reading, by & for writing.  Pass small types (int, double) by      |
| value.                                                             |
+--------------------------------------------------------------------+
| RULE 3: Large local arrays go on the stack and can overflow it.    |
| Declare them globally or use vector.                               |
+--------------------------------------------------------------------+
| RULE 4: Signed integer overflow is undefined behavior.  The        |
| compiler may assume it never happens and optimize based on that.   |
+--------------------------------------------------------------------+

These four rules interact with the walkthrough above. The pass-by-value bug from the opening example violates Rule 2. The ${200000}^2$ overflow violates Rule 1.

---

What the Code Won't Teach You

Overflow is a constraint-reading problem, not a coding problem. Before writing any code, look at the input bounds. If $n\le {10}^5$ and you multiply two values of size $n$, the product hits ${10}^{10}$—you need long long. That check belongs at problem-reading time, not at debugging time.

  Problem bounds         Mental check          Code decision
  +---------+            +----------+           +----------+
  | n<10^5  |---->  n*n  | >2*10^9  |---->      | use ll   |
  +---------+            +----------+           +----------+
  read FIRST             check BEFORE coding    choose type

The "invisible copy" is invisible precisely because C++ was designed that way. Pass-by-value is the default because it is safe—the callee cannot corrupt the caller. But in competitive programming, where performance matters and you want mutation, the safe default is the wrong default. Train yourself to always write & for container parameters, then remove it only when you consciously want a copy.

  pass by value              pass by reference
  caller      callee         caller      callee
  +------+    +------+       +------+    +------+
  | vec  |--->| copy |       | vec  |<---| ref  |
  +------+    +------+       +------+    +------+
  safe but slow              fast and direct

auto is not "let the compiler handle it"—it is "I assert I know what the compiler will deduce." If you cannot name the type that auto resolves to, you should not be using auto. This matters most for expressions involving .size(), iterator arithmetic, and ternary operators where the deduced type surprises you.

  expression             auto deduces
  +------------------+   +-------------+
  | literal 42       |-->| int         |
  | literal 42LL     |-->| long long   |
  | vec size method  |-->| size t      |  <-- unsigned
  | vec size minus 1 |-->| size t      |  <-- wraps if empty
  +------------------+   +-------------+

With those principles internalized, here is how to recognize which rule applies in practice.

---

When You'll Need This

Trigger phrases in problems and your own code:

• "function modifies a container" -> pass by reference (&)
• "read but don't modify" -> pass by const&
• "$n\le {10}^5$ and answer can be up to $n^2$" -> long long for the answer
• "product of two values up to ${10}^5$" -> cast to long long before multiplying
• "recursive DFS on large input" -> watch stack depth, or declare arrays globally
• "custom sort order" -> lambda comparator

Counter-examples—when you DON'T need the heavy tool:

• Passing a single int or double -> just use value, reference is pointless
• $n\le 1000$ and answer $\le {10}^6$ -> int is fine, long long wastes nothing but isn't needed

Pattern Fingerprint: n <= 10^5 and multiply two values -> use long longPattern Fingerprint: function takes vector param and result seems wrong -> check pass-by-reference Pattern Fingerprint: works locally, RE on judge -> stack overflow from large local arrays or deep recursion Pattern Fingerprint: works at -O0, wrong answer at -O2 -> signed integer overflow (UB)

• Small fixed-size arrays (int dx[4] = {0,1,0,-1}) -> stack is fine, no need for global

---

C++ STL Reference

This topic is about core language features, not STL containers. The table below lists the most relevant standard library utilities:

Function / Feature	Header	What it does	Notes
INT_MAX, INT_MIN	<climits>	Max/min values for int	$2^{31}-1\approx 2.1\times {10}^9$
LLONG_MAX, LLONG_MIN	<climits>	Max/min values for long long	$2^{63}-1\approx 9.2\times {10}^{18}$
numeric_limits<T>::max()	<limits>	Type-safe max value	Preferred in templates
size_t	<cstddef>	Unsigned type for sizes	Can cause bugs in size() - 1 when empty
swap(a, b)	<utility>	Swap two values	$O(1)$ for containers (move semantics)
move(x)	<utility>	Cast to rvalue reference	Avoids copies for large objects
tie(a, b) = pair	<tuple>	Unpack pair/tuple	C++11; prefer structured bindings in C++17
auto [a, b] = pair	(core language)	Structured binding	C++17
__int128	(GCC extension)	128-bit integer	No cin/cout support
__builtin_clz(x)	(GCC builtin)	Count leading zeros	UB when x == 0
__builtin_ctz(x)	(GCC builtin)	Count trailing zeros	UB when x == 0
__builtin_popcount(x)	(GCC builtin)	Count set bits	Use popcountll for long long

---

Implementation

Integer Types and Overflow

Minimal version

#include <bits/stdc++.h>
using namespace std;

#define int long long  // nuclear option: makes ALL int = long long

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

    int n; cin >> n;
    int ans = 0;
    for (int i = 0; i < n; i++) {  // Invariant: ans == sum of squares of first i elements
        int x; cin >> x;
        ans += x * x;  // safe: x*x fits in long long if x <= ~3*10^9
    }
    cout << ans << "\n";
}

Explained version

#include <bits/stdc++.h>
using namespace std;

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

    // INT_MAX  = 2^31 - 1  =  2,147,483,647       ~ 2.1 * 10^9
    // LLONG_MAX = 2^63 - 1 =  9,223,372,036,854,775,807  ~ 9.2 * 10^18

    // DANGER: int * int overflow
    int a = 200000;
    int bad = a * a;         // OVERFLOW! 4*10^10 > INT_MAX
    // The compiler computes a*a as int*int -> int (overflows)
    // Then assigns the garbage to bad.

    // FIX 1: cast one operand
    long long good1 = (long long)a * a;  // (long long * int) -> long long

    // FIX 2: multiply by 1LL
    long long good2 = 1LL * a * a;       // 1LL * int -> long long, then * int -> long long

    // FIX 3: declare as long long from the start
    long long c = 200000;
    long long good3 = c * c;             // long long * long long -> long long

    // DANGER: intermediate overflow in expressions
    int x = 100000, y = 100000, z = 100000;
    // long long bad2 = x * y * z;  // x*y overflows int FIRST, then promotes
    long long good4 = 1LL * x * y * z;  // left-to-right: (1LL*x)*y*z, all long long

    // __int128: for when even long long isn't enough
    // Needed when multiplying two long longs and checking if result fits
    // No cin/cout support -- must write custom print function
    __int128 huge = (__int128)LLONG_MAX * 2;  // > 1.8 * 10^19

    cout << good1 << " " << good2 << " " << good3 << " " << good4 << "\n";
}

Type promotion doesn't prevent intermediate overflow. In int a = 1e9, b = 1e9; long long c = a * b;, the multiplication a * b happens as int * int -> int (overflow!) before the assignment to long long. You must cast before the operation: long long c = (long long)a * b; or long long c = 1LL * a * b;.

int a = 1000000000, b = 1000000000;

long long bad = a * b;           // BUG: int * int = int (overflows), THEN assigned to long long
long long good1 = (long long)a * b;  // OK: long long * int = long long
long long good2 = 1LL * a * b;      // OK: 1LL * int = long long, then * int = long long

Quick reference—when to use what:

  Value range                Type            Example
  ---------------------------------------------------------
  up to ~2 * 10^9           int             array indices, n <= 10^5
  up to ~9 * 10^18          long long       sums of n ints, n*n products
  up to ~1.7 * 10^38        __int128        product of two long longs
  arbitrary                 Python / Java   (not C++)

---

Signed and unsigned overflow behave very differently:

  Unsigned overflow         Signed overflow

  0 --> 1 --> 2             0 --> 1 --> 2
        ...                       ...
  MAX-1 --> MAX             MAX-1 --> MAX
    |                         |
    v                         v
  MAX+1 wraps to 0         MAX+1 --> ######
  well defined              UNDEFINED
  by the standard           BEHAVIOR
                            compiler may
                            do anything

---

Pass by Value, Reference, and Const Reference

Minimal version

#include <bits/stdc++.h>
using namespace std;

// Modifies the vector in place -- caller sees the change
void deduplicate(vector<int>& v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

// Reads the vector without copying -- caller's data is safe
int sum(const vector<int>& v) {
    int s = 0;
    for (int x : v) s += x;  // Invariant: s == sum of elements seen so far
    return s;
}

// Small types: pass by value (copying an int is free)
int square(int x) { return x * x; }

int main() {
    vector<int> a = {3, 1, 4, 1, 5};
    deduplicate(a);           // a is now {1, 3, 4, 5}
    cout << sum(a) << "\n";   // 13
}

Explained version

#include <bits/stdc++.h>
using namespace std;

// RULE OF THUMB for function parameters:
//
//   Type              | When to use
//   ------------------+------------------------------------------
//   T                 | Small types (int, double, char, bool)
//   const T&          | Large types you only READ (vector, string, map)
//   T&                | Large types you need to MODIFY
//   T&&               | Rare in CP -- move semantics for advanced use

// WRONG: pass by value -- copies the entire vector
void bad_deduplicate(vector<int> v) {  // v is a COPY of the argument
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    // When this function returns, v is destroyed.
    // The caller's vector is unchanged.
}

// RIGHT: pass by reference -- operates on the original
void good_deduplicate(vector<int>& v) {  // v IS the argument
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    // Changes persist after the function returns.
}

// RIGHT: const reference for read-only access
// Compiler enforces: any attempt to modify v is a compile error.
long long compute_sum(const vector<int>& v) {
    long long s = 0;
    for (int x : v) s += x;  // Invariant: s == sum of elements processed so far
    return s;
}

// For range-based for loops:
//   for (int x : v)        -- copies each element (fine for int)
//   for (auto& x : v)      -- reference to each element (can modify)
//   for (const auto& x : v) -- read-only reference (no copy, no modify)
//   for (auto [k,v] : map) -- copies each pair (ok for small types)

int main() {
    vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

    // This does nothing to a:
    bad_deduplicate(a);
    cout << a.size() << "\n";  // still 10

    // This actually deduplicates a:
    good_deduplicate(a);
    cout << a.size() << "\n";  // now 7

    cout << compute_sum(a) << "\n";
}

---

Stack vs. Heap Memory

#include <bits/stdc++.h>
using namespace std;

// GLOBAL arrays: stored in BSS segment.
// Limit: ~256 MB (depends on judge).  Zero-initialized automatically.
int global_arr[10000000];  // 40 MB -- fine at global scope

int main() {
    // LOCAL arrays: stored on the STACK.
    // Default stack limit: 1-8 MB (often just 1 MB on Codeforces).
    // int local_arr[10000000];  // ~40 MB on stack -- SEGFAULT / stack overflow!

    // VECTOR: data stored on the HEAP.
    // Limit: whatever memory limit the judge allows (~256 MB typical).
    vector<int> heap_arr(10000000);  // 40 MB on heap -- fine anywhere

    // Recursion depth also uses the stack.
    // Each function call frame is typically 16-256 bytes.
    // With 1 MB stack: safe for ~10^4 to ~10^5 recursive calls.
    // Deep DFS on n = 10^5 nodes: might be fine.
    // Deep DFS on n = 10^6 nodes: likely stack overflow.

    // SOLUTIONS for deep recursion:
    // 1. Increase stack size: #pragma comment(linker, "/STACK:1000000000")
    //    (Windows MSVC only, doesn't work on Codeforces)
    // 2. Use iterative DFS with an explicit stack (vector<int> stk)
    // 3. On Linux judges, sometimes: ulimit -s unlimited (before running)

    // Common pitfall: Variable-Length Arrays (VLA)
    int n = 1000000;
    // int vla[n];  // GCC extension, allocated on stack -- can overflow!
    vector<int> safe(n);  // always use vector instead
}

Where things live—summary:

  Declaration site          Memory region    Zero-init?   Limit
  ---------------------------------------------------------------
  Global / static array     BSS segment      Yes          ~256 MB
  Local array (fixed size)  Stack            No           1-8 MB
  Local VLA (int a[n])      Stack            No           1-8 MB
  vector<T>                 Heap             Yes*         ~256 MB
  new / malloc              Heap             No           ~256 MB

  * vector value-initializes elements (0 for int, etc.)

Stack is typically 1–8 MB. A local int a[1000000] uses ~4 MB—it may crash with a stack overflow. Solutions: (1) declare large arrays globally, (2) use vector (heap-allocated), or (3) on some judges, add #pragma comment(linker, "/STACK:1000000000") (Windows) or ulimit -s unlimited (Linux). Safest: always use global arrays for N > 10^5.

// BAD: 4 MB on the stack -- may crash on judges with 1 MB stack limit
int main() {
    int arr[1000000];  // ~4 MB, stack-allocated
}

// GOOD option 1: global array (BSS segment, zero-initialized)
int arr[1000000];
int main() { /* use arr */ }

// GOOD option 2: vector (heap-allocated)
int main() {
    vector<int> arr(1000000);
}

---

Undefined Behavior

#include <bits/stdc++.h>
using namespace std;

int main() {
    // === SIGNED INTEGER OVERFLOW ===
    // This is THE most common UB in competitive programming.
    // Signed overflow does NOT wrap around -- it's undefined.
    // The compiler may assume it never happens and optimize accordingly.
    int a = INT_MAX;
    // int b = a + 1;  // UB! Compiler might optimize loops assuming this
                        // never happens, leading to infinite loops.

    // Unsigned overflow IS defined (wraps around mod 2^32).
    unsigned int u = UINT_MAX;
    unsigned int u2 = u + 1;  // defined: u2 == 0

    // === ARRAY OUT OF BOUNDS ===
    int arr[5] = {1, 2, 3, 4, 5};
    // int x = arr[5];   // UB -- reading past the end
    // int y = arr[-1];  // UB -- reading before the start
    // No crash guaranteed -- might return garbage, might corrupt other variables

    // === UNINITIALIZED VARIABLES ===
    int x;
    // cout << x;  // UB -- x contains whatever was on the stack
    // Globals are zero-initialized; locals are NOT.

    // === DANGEROUS BUILTINS ===
    // __builtin_clz(0)  -- UB (count leading zeros of 0 is undefined)
    // __builtin_ctz(0)  -- UB (count trailing zeros of 0 is undefined)
    // Always guard: if (x != 0) __builtin_clz(x);

    // === SHIFT OVERFLOW ===
    // Shifting by >= bit-width is UB.
    // int z = 1 << 32;  // UB for 32-bit int
    // int w = 1 << 31;  // UB! (overflow into sign bit)
    long long ok = 1LL << 40;  // fine for long long (63-bit range)

    // === MODIFYING A VARIABLE TWICE WITHOUT SEQUENCE POINT ===
    int i = 0;
    // int bad = i++ + i++;  // UB -- two modifications without sequence point

    // === HOW TO CATCH UB ===
    // Compile with sanitizers during practice (NOT in contests -- too slow):
    //   g++ -std=c++20 -O2 -fsanitize=undefined,address -o sol sol.cpp
    //
    // -fsanitize=undefined: catches signed overflow, shift UB, null deref
    // -fsanitize=address:   catches out-of-bounds, use-after-free

    cout << "No UB in this program\n";
}

---

Lambda Syntax

Minimal version

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {3, 1, 4, 1, 5, 9};

    // Sort descending
    sort(a.begin(), a.end(), [](int x, int y) { return x > y; });

    // Sort by custom key (e.g., by absolute value)
    sort(a.begin(), a.end(), [](int x, int y) {
        return abs(x) < abs(y);
    });

    // Capture by reference for DFS
    int n = 6;
    vector<vector<int>> adj(n);
    vector<bool> visited(n, false);
    vector<int> order;

    auto dfs = [&](auto self, int u) -> void {
        visited[u] = true;
        order.push_back(u);
        for (int v : adj[u])  // Invariant: all ancestors of u are already in order[]
            if (!visited[v])
                self(self, v);
    };

    dfs(dfs, 0);
}

Explained version

#include <bits/stdc++.h>
using namespace std;

int main() {
    // A lambda is an anonymous function defined inline.
    // Syntax: [capture](parameters) -> return_type { body }

    // === BASIC COMPARATOR ===
    // The simplest use: custom sort order
    vector<int> a = {3, 1, 4, 1, 5};

    // Sort descending -- lambda takes two elements, returns true if first should
    // come before second
    sort(a.begin(), a.end(), [](int x, int y) { return x > y; });
    // a is now {5, 4, 3, 1, 1}

    // === CAPTURE MODES ===
    int threshold = 3;

    // [=] capture all by VALUE (copies)
    auto count_above = [=](const vector<int>& v) {
        int cnt = 0;
        for (int x : v)  // Invariant: cnt == count of elements > threshold seen so far
            if (x > threshold) cnt++;  // uses the COPY of threshold
        return cnt;
    };

    // [&] capture all by REFERENCE
    int total = 0;
    auto accumulate_above = [&](const vector<int>& v) {
        for (int x : v)  // Invariant: total accumulates all elements > threshold seen so far
            if (x > threshold) total += x;  // modifies the REAL total
    };

    // [&total, threshold] selective capture
    // total by reference, threshold by value
    auto mixed = [&total, threshold]() {
        total += threshold;  // modifies real total, reads copy of threshold
    };

    // === RECURSIVE LAMBDA ===
    // Lambdas can't call themselves directly (the variable isn't defined yet
    // at the point of the lambda body).  The workaround: pass self as a parameter.

    int n = 5;
    vector<vector<int>> adj(n);
    adj[0] = {1, 2};
    adj[1] = {3};
    adj[2] = {4};

    vector<bool> visited(n, false);
    vector<int> order;

    // auto dfs = [&](int u) { dfs(u); };  // ERROR: dfs not yet defined

    // CORRECT: pass self explicitly
    auto dfs = [&](auto self, int u) -> void {
        visited[u] = true;
        order.push_back(u);
        for (int v : adj[u]) {  // Invariant: all previously visited neighbors of u are in order[]
            if (!visited[v]) {
                self(self, v);  // recursive call: pass self again
            }
        }
    };

    dfs(dfs, 0);  // start DFS from node 0
    // order: {0, 1, 3, 2, 4}

    // === LAMBDA AS FUNCTION OBJECT ===
    // Lambdas can be stored in variables, passed to functions, etc.
    auto is_even = [](int x) { return x % 2 == 0; };
    auto it = find_if(a.begin(), a.end(), is_even);

    // === LAMBDAS WITH STL ALGORITHMS ===
    // count_if, find_if, remove_if, any_of, all_of, none_of
    int evens = count_if(a.begin(), a.end(), [](int x) { return x % 2 == 0; });

    cout << order.size() << " " << evens << "\n";
}

Lambda Capture Pitfalls

Lambdas are powerful in CP, but capture semantics hide subtle bugs—especially around lifetimes and the difference between [=] and [&].

Dangling reference captures

When a lambda captures a local variable by reference and outlives that variable, the reference dangles—accessing it is undefined behavior:

#include <bits/stdc++.h>
using namespace std;

// BUGGY: returns a lambda holding a dangling reference
auto make_adder(int x) {
    return [&x](int y) { return x + y; };
    // x is destroyed when make_adder returns
    // The lambda's &x now points to freed stack memory -> UB
}

// FIXED: capture by value instead
auto make_adder_fixed(int x) {
    return [x](int y) { return x + y; };
    // x is copied into the lambda object -- safe to use after make_adder_fixed returns
}

int main() {
    auto bad = make_adder(10);
    // bad(5);  // UB! Reads destroyed stack variable

    auto good = make_adder_fixed(10);
    cout << good(5) << "\n";  // 15, safe
}

Capturing this—the Lifetime Trap

When you capture this in a lambda inside a struct/class, the lambda holds a pointer to the object. If the object is destroyed before the lambda runs, you get UB:

#include <bits/stdc++.h>
using namespace std;

struct Solver {
    int multiplier = 3;

    // DANGEROUS: [this] captures the pointer to this Solver object
    function<int(int)> get_transform() {
        return [this](int x) { return x * multiplier; };
        // If the Solver object is destroyed, this->multiplier is a dangling access
    }

    // SAFE: [*this] (C++17) copies the entire object into the lambda
    function<int(int)> get_transform_safe() {
        return [*this](int x) { return x * multiplier; };
    }

    // SAFE for CP: [m = multiplier] captures just the value you need
    function<int(int)> get_transform_simple() {
        return [m = multiplier](int x) { return x * m; };
    }
};

[=] vs [&]—Default Capture Modes

  [=]  default capture by VALUE         [&]  default capture by REFERENCE
  +-----------------------------+       +-----------------------------+
  | Lambda gets COPIES of all   |       | Lambda gets REFERENCES to   |
  | used variables from scope.  |       | all used variables.         |
  | Safe after scope exits.     |       | DANGEROUS after scope exits.|
  | Cannot modify originals.    |       | CAN modify originals.       |
  +-----------------------------+       +-----------------------------+
  Use when: returning lambdas,          Use when: DFS/BFS lambdas that
  storing them beyond scope.            modify visited[], dist[], etc.
  CP usage: ~5% of the time.            CP usage: ~95% of the time.

Rule of thumb for CP: Use [&] when the lambda is used and destroyed in the same scope (DFS, sort comparators, STL algorithm callbacks). Use [=] or explicit value capture [x] only when the lambda outlives the variables it captures—rare in CP.

Buggy code + fixed version: the classic contest trap

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 5;
    vector<vector<int>> adj(n);
    adj[0] = {1, 2}; adj[1] = {3}; adj[2] = {4};

    vector<int> order;
    vector<bool> visited(n, false);

    // BUGGY VERSION: capturing loop variable by reference in stored lambda
    vector<function<void()>> tasks;
    for (int u = 0; u < n; u++) {  // Invariant: tasks for nodes 0..u-1 are enqueued
        tasks.push_back([&]() {
            // BUG: u is captured by reference.
            // By the time this lambda runs, the for-loop has ended and u == n.
            // Every lambda reads u == 5 -> out of bounds!
            cout << "visiting " << u << "\n";
        });
    }
    // All tasks print "visiting 5" (or crash) -- not 0,1,2,3,4

    // FIXED VERSION: capture u by value
    vector<function<void()>> tasks_fixed;
    for (int u = 0; u < n; u++) {  // Invariant: tasks for nodes 0..u-1 are correctly captured
        tasks_fixed.push_back([u]() {
            // u is captured by VALUE -- each lambda gets its own copy
            cout << "visiting " << u << "\n";
        });
    }
    for (auto& task : tasks_fixed) task();  // Invariant: all previous tasks have executed
    // Correctly prints: visiting 0, visiting 1, ..., visiting 4
}

See also: Debugging and Stress Testing for tools that catch dangling-reference bugs at runtime.

---

Auto and Structured Bindings

#include <bits/stdc++.h>
using namespace std;

int main() {
    // === AUTO TYPE DEDUCTION ===
    // Let the compiler figure out the type.
    // Especially useful for iterators and complex return types.

    vector<int> a = {3, 1, 4, 1, 5};

    // Without auto:
    vector<int>::iterator it1 = lower_bound(a.begin(), a.end(), 3);

    // With auto (same thing, readable):
    auto it2 = lower_bound(a.begin(), a.end(), 3);

    // auto for map iterators
    map<string, int> freq;
    freq["hello"] = 3;
    freq["world"] = 7;

    // Without auto:
    // for (map<string, int>::iterator it = freq.begin(); it != freq.end(); it++)
    //     cout << it->first << ": " << it->second;

    // With auto (C++11):
    for (auto it = freq.begin(); it != freq.end(); it++)  // Invariant: all entries before it have been printed
        cout << it->first << ": " << it->second << "\n";

    // === STRUCTURED BINDINGS (C++17) ===
    // Unpack pairs, tuples, and structs into named variables.

    // Pair unpacking
    pair<int, string> p = {42, "answer"};
    auto [num, text] = p;  // num = 42, text = "answer"

    // With set/map insert (returns pair<iterator, bool>)
    auto [iter, inserted] = freq.insert({"new", 1});

    // Iterating a map with structured bindings
    for (auto& [key, val] : freq) {  // Invariant: all previous entries have been printed
        cout << key << " -> " << val << "\n";
        // key and val are references to the actual map entries
    }

    // Tuple unpacking
    tuple<int, double, string> t = {1, 3.14, "pi"};
    auto [id, value, name] = t;

    // In range-for with vector of pairs
    vector<pair<int, int>> edges = {{0, 1}, {1, 2}, {2, 3}};
    for (auto [u, v] : edges) {  // Invariant: all previous edges have been printed
        cout << u << " -> " << v << "\n";
    }

    // === CAUTION: auto& vs auto ===
    // auto [k, v] : map     -- copies each pair (ok for small types)
    // auto& [k, v] : map    -- references to actual entries (can modify)
    // const auto& [k, v] : map  -- read-only references (no copy, no modify)

    for (auto& [key, val] : freq) {  // Invariant: all previous entries have been doubled
        val *= 2;  // doubles all values in the map
    }
}

---

Templates and Operator Overloading

#include <bits/stdc++.h>
using namespace std;

// === CUSTOM STRUCT WITH COMPARISON ===
// Required for: set<Point>, map<Point,...>, sort by custom order

struct Point {
    int x, y;

    // operator< is required for set, map, and sort (default comparator)
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }

    // operator== is sometimes needed (e.g., for unordered_set with custom hash)
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// === CUSTOM COMPARATOR FOR priority_queue ===
// priority_queue is a MAX-heap by default.
// To make a MIN-heap, provide a "greater" comparator.

struct Event {
    int time, type;
};

// Functor comparator (struct with operator())
struct CompareEvent {
    bool operator()(const Event& a, const Event& b) const {
        return a.time > b.time;  // note: > for min-heap (reversed!)
    }
};

// === SIMPLE TEMPLATE FUNCTION ===
// Reusable utility -- works for any type with operator<
template<typename T>
T clamp_val(T val, T lo, T hi) {
    return max(lo, min(val, hi));
}

int main() {
    // Using Point in set (uses operator<)
    set<Point> pts;
    pts.insert({1, 2});
    pts.insert({3, 1});
    pts.insert({1, 2});  // duplicate, not inserted
    cout << pts.size() << "\n";  // 2

    // Using sort with lambda comparator
    vector<Point> v = {{3, 1}, {1, 2}, {2, 3}};
    sort(v.begin(), v.end(), [](const Point& a, const Point& b) {
        return a.y < b.y;  // sort by y coordinate
    });

    // Min-heap with custom comparator
    priority_queue<Event, vector<Event>, CompareEvent> pq;
    pq.push({5, 1});
    pq.push({2, 0});
    pq.push({8, 1});
    cout << pq.top().time << "\n";  // 2 (minimum)

    // Alternative: lambda comparator for priority_queue (C++20 or with decltype)
    auto cmp = [](const Event& a, const Event& b) {
        return a.time > b.time;
    };
    priority_queue<Event, vector<Event>, decltype(cmp)> pq2(cmp);

    // Template function usage
    int x = clamp_val(15, 0, 10);  // 10
    double d = clamp_val(3.7, 1.0, 5.0);  // 3.7

    cout << x << " " << d << "\n";
}

Const Correctness

In competitive programming, const isn't just "good practice"—it prevents accidental mutation bugs and unlocks compiler optimizations. Understanding const vs. constexpr also matters for compile-time constants like MAXN.

const vs constexpr

#include <bits/stdc++.h>
using namespace std;

// const: value cannot be changed after initialization (runtime or compile-time)
const int MOD = 1e9 + 7;           // compile-time constant
const int INF = numeric_limits<int>::max();  // compile-time

// constexpr: MUST be evaluable at compile time
// The compiler can use it in array sizes, template parameters, etc.
constexpr int MAXN = 200005;
constexpr long long LLINF = 1e18;

// constexpr function: evaluated at compile time if possible
constexpr long long factorial(int n) {
    long long res = 1;
    for (int i = 2; i <= n; i++) res *= i;  // Invariant: res == i! after each iteration
    return res;
}

int a[MAXN];                       // OK: MAXN is constexpr
constexpr long long f10 = factorial(10);  // computed at COMPILE TIME

int main() {
    // const prevents accidental modification
    const int n = 5;
    // n = 6;  // compile error -- caught immediately

    // In loops, const reference avoids copies AND prevents mutation:
    vector<vector<int>> grid = {{1,2},{3,4},{5,6}};
    for (const auto& row : grid) {  // Invariant: all previous rows processed read-only
        // row.push_back(7);  // compile error -- const prevents this
        for (int x : row) cout << x << " ";  // Invariant: all previous elements in row printed
    }
    cout << "\n";
}

Why const int& matters for function parameters

#include <bits/stdc++.h>
using namespace std;

// BAD: copies the entire vector every call -- O(n) per call
long long sum_bad(vector<int> v) {
    long long s = 0;
    for (int x : v) s += x;  // Invariant: s == sum of elements processed
    return s;
}

// GOOD: no copy, and compiler enforces read-only access
long long sum_good(const vector<int>& v) {
    long long s = 0;
    for (int x : v) s += x;  // Invariant: s == sum of elements processed
    return s;
    // v.push_back(1);  // compile error -- const prevents accidental modification
}

// For strings too -- very common in CP:
int count_vowels(const string& s) {
    int cnt = 0;
    for (char c : s)  // Invariant: cnt == number of vowels in s[0..i-1]
        if (string("aeiou").find(c) != string::npos) cnt++;
    return cnt;
}

int main() {
    vector<int> a = {1, 2, 3, 4, 5};
    cout << sum_good(a) << "\n";  // no copy
    // sum_good cannot accidentally modify a -- compiler guarantees it
}

const member functions

When you define a struct with operator< for use in set/map, the comparison operator must be const:

struct Point {
    int x, y;

    // The 'const' at the end means: this function does not modify the Point object.
    // Required by set/map -- they pass elements as const references internally.
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }

    // Without 'const', this won't compile when used in set<Point>:
    // bool operator<(const Point& other) { ... }  // ERROR in set/map context
};

Contest-practical const tips

+---------------------------------------------------------------------+
| CONST CORRECTNESS QUICK RULES                                       |
|=====================================================================|
| 1. Function reads a container? -> const T&                          |
| 2. Function modifies a container? -> T&                             |
| 3. Array size known at compile time? -> constexpr int MAXN = ...    |
| 4. Named constant (MOD, INF)? -> const or constexpr                 |
| 5. Struct used in set/map? -> operator< must be const               |
| 6. Range-for read-only? -> for (const auto& x : v)                 |
+---------------------------------------------------------------------+

---

How Compiler Flags Affect Undefined Behavior

Compiler flags matter because the same code can behave differently depending on optimization level. Code that "works" during practice may produce wrong answers or crash on the judge.

See also: Debugging and Stress Testing for a systematic approach to finding bugs, and Fast I/O and Pragmas for pragmas that affect compilation.

-fsanitize=undefined—What It Catches

The UndefinedBehaviorSanitizer (UBSan) instruments your binary to detect UB at runtime. It catches:

+----------------------------------+------------------------------------------+
| UB Type                          | Example                                  |
+----------------------------------+------------------------------------------+
| Signed integer overflow          | int x = INT_MAX; x++;                    |
| Division by zero                 | int y = 1 / 0;                           |
| Shift out of range               | int z = 1 << 32;                         |
| Out-of-bounds array access       | int a[5]; a[10] = 1; (with -fsanitize=  |
|                                  |   address too)                           |
| Null pointer dereference         | int* p = nullptr; *p = 1;                |
| Misaligned pointer access        | accessing int via char* at odd address   |
| __builtin_clz(0)                 | UB: leading zeros of 0 is undefined      |
+----------------------------------+------------------------------------------+

# Compile with UBSan for practice:
g++ -std=c++20 -O2 -fsanitize=undefined -o sol sol.cpp

# Example UBSan output:
# sol.cpp:12:15: runtime error: signed integer overflow:
# 2000000000 + 2000000000 cannot be represented in type 'int'

-O2 vs -O0—How Optimization Exposes UB

The compiler is permitted to assume UB never happens. At -O2, it uses this assumption to optimize, which can silently break buggy code:

#include <bits/stdc++.h>
using namespace std;

// This code behaves DIFFERENTLY at -O0 vs -O2:
bool is_valid(int x) {
    // The compiler sees: x + 1 > x.
    // For signed int, overflow is UB, so the compiler assumes it never happens.
    // Therefore x + 1 > x is ALWAYS true (under no-UB assumption).
    // At -O2, the compiler may optimize this to: return true;
    return x + 1 > x;
}

int main() {
    cout << is_valid(INT_MAX) << "\n";
    // At -O0 (no optimization): likely prints 0 (wraps via two's complement)
    // At -O2 (optimized):       likely prints 1 (compiler assumes no overflow)
    // BOTH are "correct" because signed overflow is UB -- any result is legal
}

Practical example: code that works in debug but breaks in release:

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Searching for a value -- with an overflow bug
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};
    int n = 8;

    // BUGGY binary search: lo + hi can overflow for large indices
    int lo = 0, hi = n - 1;
    int target = 7;
    int result = -1;

    while (lo <= hi) {  // Invariant: if target exists, it is in arr[lo..hi]
        int mid = (lo + hi) / 2;  // BUG: lo + hi can overflow if both are large
        // At -O0: might work because overflow wraps predictably
        // At -O2: compiler may assume lo+hi never overflows, producing wrong mid
        if (arr[mid] == target) { result = mid; break; }
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }

    // FIXED: use subtraction to avoid overflow
    lo = 0; hi = n - 1; result = -1;
    while (lo <= hi) {  // Invariant: if target exists, it is in arr[lo..hi]
        int mid = lo + (hi - lo) / 2;  // SAFE: no overflow possible
        if (arr[mid] == target) { result = mid; break; }
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }

    cout << result << "\n";
}

-Wall -Wextra—Warnings That Catch Common Bugs

# Always compile with warnings during practice:
g++ -std=c++20 -O2 -Wall -Wextra -Wshadow -o sol sol.cpp

Key warnings and what they catch:

+---------------------+--------------------------------------------------+
| Flag                | What it catches                                  |
+---------------------+--------------------------------------------------+
| -Wall               | Uninitialized variables, missing return values,  |
|                     | unused variables, implicit conversions            |
+---------------------+--------------------------------------------------+
| -Wextra             | Unused parameters, signed/unsigned comparison,   |
|                     | empty loop bodies                                |
+---------------------+--------------------------------------------------+
| -Wshadow            | Variable shadowing (local hides outer variable)  |
|                     | e.g., int n = 5; { int n = 3; } // warning!     |
+---------------------+--------------------------------------------------+
| -Wconversion        | Implicit narrowing conversions (ll -> int)       |
|                     | Catches: long long x = ...; int y = x;          |
+---------------------+--------------------------------------------------+

// Example: -Wshadow catches this common bug
#include <bits/stdc++.h>
using namespace std;

int n;  // global

void solve() {
    int n;  // WARNING: shadows global 'n'
    cin >> n;
    // ... rest of solve uses local n, but other functions see global n (still 0)
}

Recommended compilation commands

# PRACTICE (maximum safety, ~3-5x slower):
g++ -std=c++20 -O2 -Wall -Wextra -Wshadow -Wconversion \
    -fsanitize=undefined,address \
    -D_GLIBCXX_DEBUG -o sol sol.cpp

# CONTEST (fast, matches judge):
g++ -std=c++20 -O2 -o sol sol.cpp

# STRESS TEST (need speed + some safety):
g++ -std=c++20 -O2 -Wall -Wextra -o sol sol.cpp

---

Operations Reference

Every language feature covered above has a cost. Use this table to judge at a glance whether a call is free or hiding a copy:

Operation	Cost	Notes
Pass int by value	$O(1)$	4 bytes copied
Pass vector<int> of size $n$ by value	$O(n)$	Full copy: heap alloc + $n$ copies
Pass vector<int> by reference	$O(1)$	Just a pointer internally
int * int	$O(1)$	May overflow if result > $2^{31}-1$
(long long)a * b	$O(1)$	Safe up to $\approx 9.2\times {10}^{18}$
__int128 multiply	$O(1)$	Emulated on most platforms (~2-4x slower)
Lambda creation	$O(k)$	$k$ = number of captured-by-value variables
Lambda call	$O(1)$	Same as regular function call
auto [a,b] = pair	$O(1)$	Structured binding, compile-time sugar
Stack allocation (int a[n])	$O(1)$	Just moves stack pointer; limited to ~1-8 MB
Heap allocation (vector(n))	$O(n)$	Zero-initializes; limited to ~256 MB
Global array access	$O(1)$	Stored in BSS; zero-initialized at program start

---

Patterns and Tricks

Pattern 1—The #define int long long Trick

When overflow is a concern everywhere and you don't want to think about individual casts, some contestants redefine int globally:

#define int long long
int32_t main() {   // must use int32_t for main's return type
    int n; cin >> n;
    // all "int" variables are now long long
}

Tradeoffs: uses 2× memory for arrays, slightly slower. At CF 800–1300 level this almost never matters. For tight memory limits, prefer targeted long long declarations.

Referenced in: almost every problem at CF 800+ level.

---

Pattern 2—Safe Multiplication with 1LL *

When you need a long long result from int operands:

int a = 100000, b = 100000;
long long product = 1LL * a * b;       // safe
long long sum_sq  = 1LL * n * (n + 1) / 2;  // safe for n up to ~3*10^9

The 1LL forces the first multiplication to produce long long, and left-to-right evaluation keeps the whole chain in long long after that.

  1LL * a * b    type promotion left to right

  +-----+     +-------+     +-------+     +--------+
  | 1LL | --> | 1LL*a | --> | res*b | --> | result |
  | ll  |     | ll    |     | ll    |     | ll     |
  +-----+     +-------+     +-------+     +--------+
    ^              ^              ^
    |              |              |
  long long     int promotes   int promotes
  literal       to ll          to ll

  Compare with  a * b  where both are int

  +-----+     +--------+
  | a*b | --> | result |  <-- OVERFLOW if > 2*10^9
  | int |     | int    |
  +-----+     +--------+

Referenced in: CF 1A (Theatre Square), CF 1547B (Alphabetical Strings).

---

Pattern 3—Recursive Lambda for DFS/BFS

Avoid polluting the global scope with DFS variables. Keep everything local:

int n; cin >> n;
vector<vector<int>> adj(n);
// ... read edges ...

vector<int> depth(n, -1);
auto dfs = [&](auto self, int u, int d) -> void {
    depth[u] = d;
    for (int v : adj[u])  // Invariant: depth[u] is set; processing unvisited neighbors
        if (depth[v] == -1)
            self(self, v, d + 1);
};
dfs(dfs, 0, 0);

This pattern captures adj and depth by reference. No global state needed.

Referenced in: any DFS/BFS problem—CF 1324C (Frog Jumps), CF 1385E (Directing Edges).

---

Pattern 4—Lambda Comparators for Sorting

Sort by custom criteria without writing a full comparator struct:

vector<pair<int,int>> events;  // (time, type)

// Sort by time ascending, break ties by type descending
sort(events.begin(), events.end(), [](auto& a, auto& b) {
    if (a.first != b.first) return a.first < b.first;
    return a.second > b.second;
});

For priority_queue, the comparator is inverted—return true if a should come after b:

// Min-heap by first element
auto cmp = [](auto& a, auto& b) { return a.first > b.first; };
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);

Referenced in: CF 1353D (Constructing the Array), CF 1000C (Covered Points Count).

---

Pattern 5—Global Arrays for Large Memory

When you need arrays larger than ~1 MB:

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2000005;
int a[MAXN];          // 8 MB at global scope -- fine
long long dp[MAXN];   // 16 MB at global scope -- fine
bool visited[MAXN];   // 2 MB -- fine

int main() {
    // DON'T do this inside main:
    // int big[2000005];  // stack overflow!
    // DO use global arrays or vectors instead.
    int n; cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];  // Invariant: a[0..i-1] are read
}

Referenced in: any problem with $n\le 2\times {10}^6$.

---

Pattern 6—Structured Bindings for Clean Graph Code

Structured bindings make weighted graph code much cleaner:

// Dijkstra with structured bindings
vector<vector<pair<int,long long>>> adj(n);  // adj[u] = {(v, w), ...}

vector<long long> dist(n, LLONG_MAX);
priority_queue<pair<long long,int>, vector<pair<long long,int>>,
               greater<>> pq;
dist[0] = 0;
pq.push({0, 0});

while (!pq.empty()) {  // Invariant: dist[u] is finalized for all popped nodes with d == dist[u]
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;
    for (auto [v, w] : adj[u]) {  // Invariant: dist[u] is optimal; relaxing outgoing edges
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});
        }
    }
}

Compare without structured bindings: pq.top().first, pq.top().second, adj[u][i].first, adj[u][i].second—harder to read, easier to swap accidentally.

Referenced in: CF 20C (Dijkstra?), CF 1473E (Minimum Path).

When NOT to Use These Features

Every tool here has a situation where it makes things worse. Here are the common anti-patterns:

#define int long long—when it's dangerous:

• When the problem has tight memory limits (e.g., 32 MB). The #define doubles every array from 4 bytes/element to 8 bytes/element—a 10^6 array jumps from 4 MB to 8 MB.
• When using bitwise operations that depend on 32-bit width. 1 << 31 is UB for signed 32-bit int, but (long long)1 << 31 is fine—yet ~0 changes meaning from 32 to 64 set bits.
• When interfacing with C library functions that expect actual int (rare in CP).

[&] capture—when it's dangerous:

• When the lambda is stored and used after the captured variables are destroyed (see Lambda Capture Pitfalls above).
• When the lambda is returned from a function—local variables are gone.
• In multithreaded contexts (rare in CP, but exists in some interactive problems).

auto—when it hides bugs:

• auto x = v.size() - 1; deduces size_t (unsigned)—wraps to 2^64 - 1 if v is empty. Use int x = (int)v.size() - 1; instead.
• auto product = a * b; where a, b are int—deduces int, doesn't prevent overflow. Write long long product = 1LL * a * b; explicitly.

Global arrays—when they cause problems:

• When you need multiple test cases (t test cases in one run) and forget to reset the global array between cases. memset or re-initialization is required; with local vector, destruction is automatic.
• When the array size depends on input—globals must be sized for worst case, wasting memory if most test cases are small.

using namespace std;—when it collides:

• When you define a variable or function named count, next, prev, data, left, right, distance, or size—these collide with std:: names. Usually fine in CP, but causes cryptic errors when it does collide.

See also: Bit Manipulation for cases where #define int long long interacts poorly with bitwise operations.

---

Mnemonic: "Reference Large, Value sMall, Long Long when products are tall"—the three rules that prevent the majority of beginner WAs.

Contest Cheat Sheet

+---------------------------------------------------------------------+
| C++ LANGUAGE ESSENTIALS CHEAT SHEET                                 |
|=====================================================================|
| INTEGER OVERFLOW                                                    |
|  INT_MAX  ~ 2.1 * 10^9     LLONG_MAX ~ 9.2 * 10^18                |
|  Safe multiply: 1LL * a * b    or   (long long)a * b               |
|  Nuclear option: #define int long long  +  int32_t main()           |
|---------------------------------------------------------------------|
| PASS BY REFERENCE                                                   |
|  Read-only:  void f(const vector<int>& v)                          |
|  Modify:     void f(vector<int>& v)                                |
|  Small type: void f(int x)    // value is fine                      |
|---------------------------------------------------------------------|
| MEMORY LAYOUT                                                       |
|  Global array: BSS, ~256 MB, zero-init                              |
|  Local array:  stack, 1-8 MB, NOT zero-init                         |
|  vector<T>:    heap, ~256 MB, zero-init                             |
|  Recursion:    ~10^4 to 10^5 deep before stack overflow             |
|---------------------------------------------------------------------|
| LAMBDAS                                                             |
|  Comparator:   [](int a, int b) { return a > b; }                  |
|  Capture all:  [&](int x) { ... }  // by ref (most common in CP)   |
|  Recursive:    auto f = [&](auto self, int u) -> void {             |
|                    self(self, v);  };                                |
|---------------------------------------------------------------------|
| STRUCTURED BINDINGS (C++17)                                         |
|  auto [a, b] = make_pair(1, 2);                                    |
|  for (auto& [key, val] : my_map) { ... }                           |
|---------------------------------------------------------------------|
| UNDEFINED BEHAVIOR (common)                                         |
|  Signed overflow, __builtin_clz(0), arr[-1], uninitialized var     |
|  Debug: g++ -fsanitize=undefined,address -std=c++20                 |
+---------------------------------------------------------------------+

If I Had 5 Minutes

• Check overflow: if n <= 10^5 and you multiply two values, use long long or 1LL *
• Check pass-by-ref: every function taking vector/string/map should use & or const&
• Check array location: arrays > 10^5 elements -> declare globally or use vector
• Check comparators: use < not <=; use > not >= (strict weak ordering)
• Check edge cases: empty containers with .size() - 1, zero inputs, n = 1

"Before You Code" Checklist

Before writing any C++ solution, run through these five checks:

• [ ] 1. Types: Will any intermediate product exceed 2 x 10^9? -> long long
• [ ] 2. Signatures: Does every function that takes a container use & or const&?
• [ ] 3. Memory: Any array > 10^5 elements declared locally? -> Move to global or use vector
• [ ] 4. Edge cases: Does the code handle n = 0, n = 1, empty input?
• [ ] 5. UB check: Any v.size() - 1 on possibly-empty containers? Any 1 << 31?

---

Gotchas and Debugging

1. The size_t Subtraction Trap

vector::size() returns size_t (unsigned). If the vector is empty:

vector<int> v;
for (int i = 0; i < v.size() - 1; i++) { ... }
// v.size() - 1 = 0u - 1 = 18446744073709551615 (unsigned wraparound!)
// Loop runs ~2^64 times -> TLE or crash

Fix: Cast to int first: for (int i = 0; i < (int)v.size() - 1; i++)

  size_t is unsigned -- cannot hold negative values

  v has 5 elements            v is empty
  +---+                       +---+
  | 5 | size                  | 0 | size
  +---+                       +---+
    |  minus 1                  |  minus 1
    v                           v
  +---+                       +---------------------+
  | 4 | all good              | 18446744073709551615 |
  +---+                       +---------------------+
                               unsigned wraparound
                               loop runs forever

---

2. int Overflow in Comparators

// WRONG: overflow when a and b have opposite signs
sort(v.begin(), v.end(), [](int a, int b) { return a - b < 0; });

// RIGHT: use direct comparison
sort(v.begin(), v.end(), [](int a, int b) { return a < b; });

Never subtract in comparators—the difference can overflow.

---

3. Forgetting 1LL in Formulas

// WRONG: n*(n+1)/2 overflows for n = 100000 (int * int = int)
int n = 100000;
long long ans = n * (n + 1) / 2;  // overflow BEFORE assignment to long long

// RIGHT: force long long early
long long ans = 1LL * n * (n + 1) / 2;

---

4. Lambda Capture Dangling References

auto make_adder(int x) {
    // DANGER: x is a local variable
    return [&x](int y) { return x + y; };
    // When make_adder returns, x is destroyed.
    // The lambda holds a dangling reference -> UB
}
// FIX: capture by value [x] or [=]

In competitive programming, this rarely happens because lambdas are usually defined and used in the same scope. But beware if you return lambdas.

---

5. Uninitialized Local Variables

int dp[1005][1005];  // local -- contains GARBAGE
// Must memset or fill before use:
memset(dp, 0, sizeof dp);       // set all bytes to 0
memset(dp, -1, sizeof dp);      // set all bytes to 0xFF -> -1 for int
memset(dp, 0x3f, sizeof dp);    // set to ~10^9 (useful as "infinity")

Global arrays are automatically zero-initialized. Local arrays are not.

---

6. Strict Weak Ordering Violation

Custom comparators must satisfy strict weak ordering (irreflexive, asymmetric, transitive). Violating this is UB and causes crashes:

// WRONG: returns true for equal elements (not irreflexive)
sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });

// RIGHT: use strict less-than
sort(v.begin(), v.end(), [](int a, int b) { return a < b; });

Use <, not <=. Use >, not >=. This applies to sort, set, map, and priority_queue.

---

7. auto Hides Type Bugs

auto x = 1;        // int
auto y = 1LL;      // long long
auto z = 1.0;      // double
auto w = 1.0f;     // float

// Surprise: auto with mixed arithmetic
int a = 1000000;
auto sq = a * a;   // auto deduces int (because a*a is int*int)
                    // overflow! auto doesn't save you

auto deduces the type of the expression, which follows the usual promotion rules. If both operands are int, the result is int—even if it overflows.

---

8. Debugging Flags for Practice

# Recommended compilation for practice sessions:
g++ -std=c++20 -O2 -Wall -Wextra -Wshadow \
    -fsanitize=undefined,address \
    -D_GLIBCXX_DEBUG \
    -o sol sol.cpp

# -Wall -Wextra -Wshadow : catch common warnings
# -fsanitize=undefined    : catch signed overflow, bad shifts, null deref
# -fsanitize=address      : catch out-of-bounds, use-after-free
# -D_GLIBCXX_DEBUG        : enable STL debug mode (bounds checking on vector[])

For contest submissions, use just -std=c++20 -O2. Sanitizers slow down execution by 2–10×.

---

Mental Traps

Trap 1—"It works on my machine, so there is no bug."

Signed integer overflow is undefined behavior, not a predictable wraparound. Your local build at -O0 may wrap via two's complement and accidentally produce a plausible answer. The judge compiles at -O2, assumes overflow never happens, and may delete your bounds check entirely—turning a bug into a silently wrong result. "Works locally, WA on judge" is the classic symptom.

  WRONG view              RIGHT view
  +------------+          +------------+
  | int a * b  |          | int a * b  |
  | overflow   |          | overflow   |
  +-----+------+          +-----+------+
        |                       |
        v                       v
  +-----------+           +-----------+
  | wraps to  |           | UNDEFINED |
  | negative  |           | BEHAVIOR  |
  +-----+-----+           +-----+-----+
        |                       |
        v                       v
   works at O0             O2 may delete
   fails at O2             your if check

Trap 2—"I will just use long long everywhere and not think about it."

#define int long long converts your value types but does not touch return types from the standard library. v.size() still returns size_t, which is unsigned—subtracting 1 from zero wraps to a massive positive number. The macro also doubles memory for every array, risking MLE on tight limits. Wholesale long long is a shortcut, not a substitute for reading the constraints.

  #define int long long
  +----------+---------+
  | int x    | --> ll  |  values safe
  | int y    | --> ll  |  values safe
  +----------+---------+
       |
       v
  +-------------------+
  | v.size() returns  |
  | size_t UNSIGNED   |  <-- NOT changed
  |                   |
  | 0u minus 1 wraps  |
  | to 2^64 minus 1   |
  +-------------------+

Trap 3—"References are just pointers, I get it."

You write & in function parameters but forget range-for loops. for (auto x : v) copies every element; for (auto& x : v) gives a reference. For a vector<string>, the copy version is silently $O(n\cdot L)$ slower—it will not show up in a profiler because each copy looks cheap individually.

  WRONG - copies              RIGHT - references
  for (auto x : v)            for (auto& x : v)

  +------+    +------+        +------+
  | v[0] |--->| copy |        | v[0] |<---+
  +------+    +------+        +------+    |
  | v[1] |--->| copy |        | v[1] |<---+-- x is alias
  +------+    +------+        +------+    |
  | v[2] |--->| copy |        | v[2] |<---+
  +------+    +------+        +------+
  N copies made               zero copies

What Would You Do If...?

Q: Your solution passes all local tests but gets Runtime Error (RE) on Codeforces?

Check in this order: (1) Large local arrays causing stack overflow—move them to global scope or use vector. (2) Array index out of bounds—add -fsanitize=address locally to reproduce. (3) Deep recursion (> 10^5 levels)—convert to iterative with an explicit stack. (4) Division by zero on an edge case.

Q: Your solution gives the right answer locally but Wrong Answer (WA) on the judge?

Most likely integer overflow. Compile with -fsanitize=undefined to check. Also verify: (1) Are you reading the input format correctly? (2) Is v.size() - 1 wrapping unsigned? (3) Is your comparator violating strict weak ordering?

Q: Your solution gets Time Limit Exceeded (TLE) and you suspect it's not the algorithm?

Check: (1) Passing vector/string by value in a function called $O(n)$ times—that's $O(n^2)$ hidden copies. (2) Using endl instead of "\n"—endl flushes the buffer each time. (3) for (auto x : v) copying large objects—use auto& x. See Fast I/O and Pragmas for I/O optimization.

The Mistake That Teaches

Round 834, Div. 3. Twenty minutes into the contest.

Alex had problem C figured out. A simple greedy: sort the array, pair the smallest with the largest, compute the maximum difference. Easy AC. They coded it in four minutes flat—clean lambda comparator, structured bindings, the works.

int n; cin >> n;
vector<int> a(n);
for (auto& x : a) cin >> x;  // Invariant: elements 0..i-1 are read
sort(a.begin(), a.end());
long long ans = 0;
for (int i = 0; i < n / 2; i++)  // Invariant: ans == sum of (a[n-1-j] - a[j]) for j in 0..i-1
    ans += a[n - 1 - i] - a[i];
cout << ans << "\n";

Wrong Answer on test 3. Alex stared. The logic was obviously correct. They stress-tested against a brute force—perfect match for 100 random tests. They submitted again. WA again.

Fifteen minutes of panic later, they spotted it: a[n - 1 - i] - a[i]. Both operands are int. The values go up to ${10}^9$. The difference can reach $2\times {10}^9$—which fits in int—but ans accumulates n/2 such differences, and with $n=2\times {10}^5$, the sum reaches ${10}^{14}$. The += does long long += int—safe. But a[n-1-i] - a[i] is computed as int - int -> int first. If a[n-1-i] = 1e9 and a[i] = -1e9, the difference is $2\times {10}^9$, which overflows int before the long long ever sees it.

The fix: ans += (long long)a[n - 1 - i] - a[i]; One cast. Twenty minutes of contest time burned.

The lesson: overflow doesn't happen in the variable you declared long long. It happens in the expression that feeds it. The right side of += is evaluated before the assignment. Always check the types of intermediate expressions, not just the destination variable.

---

Self-Test

Answer these without looking above:

• [ ] What is the result of int a = 1e5; long long b = a * a;? Explain why it is not ${10}^{10}$.
• [ ] Write a function that takes a vector<int> and doubles every element in-place. Get the signature right on the first try.
• [ ] Explain why int arr[500000] inside main() might crash on Codeforces but work locally.
• [ ] Given vector<int> v; (empty), what is the value and type of v.size() - 1?
• [ ] Write a recursive DFS lambda that captures adj, visited, and order by reference. Include the auto self pattern.
• [ ] Name two forms of undefined behavior that produce no compiler warning and no runtime crash—just a wrong answer.
• [ ] Why does #define int long long require you to change main to int32_t main()?

Debug This!

Find the bug in each snippet.

Bug 1: The Invisible TLE

void process(vector<int> data) {
    sort(data.begin(), data.end());
    // ... process sorted data ...
}

int main() {
    int q; cin >> q;
    vector<int> a(100000);
    for (auto& x : a) cin >> x;
    while (q--) {
        process(a);  // called up to 10^5 times
    }
}

Answer

process takes vector<int> by value—it copies all 100,000 elements on every call. With q = 10^5 calls, that's 10^{10} copy operations -> TLE.

Fix: void process(vector<int>& data) or void process(const vector<int>& data) if you don't need to sort the original.

Bug 2: The Off-By-2^64

vector<int> v = {1, 2, 3};
for (int i = 0; i <= v.size() - 1; i++) {
    cout << v[i] << " ";
}

// Now try with an empty vector:
vector<int> w;
for (int i = 0; i <= w.size() - 1; i++) {
    cout << w[i] << " ";  // what happens?
}

Answer

w.size() is 0 (type size_t, unsigned). 0u - 1 wraps to 18446744073709551615. The loop condition i <= 18446744073709551615 is always true -> infinite loop / out-of-bounds access -> TLE or RE.

Fix: for (int i = 0; i < (int)w.size(); i++) or guard with if (!w.empty()).

Bug 3: The Sneaky Overflow

int n = 100000;
int sum_of_squares = 0;
for (int i = 1; i <= n; i++) {
    sum_of_squares += i * i;  // is this safe?
}
cout << sum_of_squares << "\n";

Answer

i * i for i = 100000 is 10^{10}, which overflows int (max ~2.1 x 10^9). Even before that, partial sums overflow. The variable sum_of_squares is int, so even the accumulation overflows.

Fix: Use long long sum_of_squares = 0; and either 1LL * i * i or declare i as long long.

Bug 4: The Silent Comparator Crash

vector<int> v = {3, 1, 4, 1, 5, 9};
sort(v.begin(), v.end(), [](int a, int b) {
    return a >= b;  // "greater than or equal"
});

Answer

The comparator uses >= instead of >. This violates strict weak ordering (it's not irreflexive: cmp(x, x) returns true). This is undefined behavior in std::sort and can cause crashes, infinite loops, or wrong results—the behavior varies by compiler and data.

Fix: return a > b; (strict greater-than for descending sort).

---

Practice Problems

Problems where C++ language knowledge—not algorithm knowledge—is the key:

#	Problem	Source	Difficulty	Key Idea
1	Theatre Square	CF 1A	800	Integer overflow on $n\cdot m$; needs long long
2	Way Too Long Words	CF 71A	800	String basics, string::size() returns size_t
3	Watermelon	CF 4A	800	Edge case + basic types; warm-up
4	Next Round	CF 158A	800	Array pass-by-reference practice
5	Sum of Round Numbers	CF 1352A	800	Integer decomposition, clean I/O
6	Nearly Lucky Number	CF 110A	800	String iteration, count_if with lambda
7	Maximum Product	CF 1435B	1200	Overflow trap: product of five values can exceed int
8	Yet Another Palindrome Problem	CF 1324B	1100	Map with structured bindings; pass-by-ref for speed

Rating Progression

How your relationship with C++ language features evolves as you improve:

• At CF 1200: int overflow stops catching you off guard—you instinctively prefix with 1LL * or reach for #define int long long. You pass containers by reference. These two habits alone cut debugging time in half.
• At CF 1500: You write lambda comparators without looking anything up, and recursive DFS lambdas with [&](auto self, ...) feel natural. You know when auto helps versus when it hides a type bug. You understand stack vs. heap and never declare large arrays locally.
• At CF 1800: You catch UB before it bites—practice sessions compile with -fsanitize=undefined. constexpr for compile-time constants, structured bindings everywhere, and <= in a comparator is a mistake you don't make anymore.
• At CF 2100: You think about memory layout and cache effects. __int128 is a tool you reach for when needed. You understand how -O2 can transform (and break) your code, and you write const correctly throughout.

---

Further Reading

• C++ Reference—Type sizes—authoritative source for type widths and ranges
• C++ Reference—Lambda expressions—full lambda syntax including C++20 template lambdas
• C++ Reference—Structured bindings—complete rules for binding declarations
• C++ Reference—Undefined behavior—comprehensive UB list
• GCC Builtin Functions—__builtin_clz, __builtin_popcount, etc.
• Codeforces Blog: Avoiding Integer Overflow—common overflow patterns and fixes

---

What to Solve Next

• Ready to practice? 1100–1400 Ladder—problems where language mastery is the bottleneck
• Need fast I/O? Fast I/O and Pragmas—make your I/O fast enough to not TLE
• Deeper into STL: STL Containers · STL Algorithms—the data structures and algorithms you'll reach for in every contest
• Bit-level control: Bit Manipulation—bitwise operations, masks, and builtins
• When it compiles but fails: Debugging and Stress Testing—systematic approaches for wrong answers
• Learn techniques: Essential Techniques—the algorithmic toolkit that builds on these language fundamentals

---

Next Up: Fast I/O and Pragmas →