Chapter 48 of 48

C++ for Competitive Programming

Competitive programming (CP) means solving well-defined algorithmic problems under a time limit, on judges such as Codeforces, CodeChef, AtCoder and LeetCode, and in contests like ICPC. It is also how many Indian companies run their online assessments for placements. Your program reads input, prints output, and must finish within a time limit (often 1–2 seconds) and a memory limit (often 256 MB).

C++ is the most popular CP language for three reasons: it is fast, the STL gives you ready-made, well-tested data structures and algorithms, and you have precise control over types and memory. This final chapter collects everything from the earlier chapters into a practical CP toolkit: the standard template, fast I/O, choosing the right data type, estimating complexity, the STL operations you will use daily, classic code patterns, and the bugs that cost people "Wrong Answer" and "Time Limit Exceeded" verdicts.


How an Online Judge Works

  your source  ──▶  judge compiles it (e.g. g++ -O2 -std=c++XX)
                          │
                          ▼
     hidden test 1 ──▶  run with time + memory limit  ──▶ compare output
     hidden test 2 ──▶            ...                 ──▶ compare output
          ...
                          │
                          ▼
   Accepted (AC) · Wrong Answer (WA) · Time Limit Exceeded (TLE)
   Memory Limit Exceeded (MLE) · Runtime Error (RE) · Compilation Error (CE)

A program is accepted only if, for every hidden test, it prints exactly the expected output (usually ignoring trailing whitespace) within the time and memory limits. Passing the sample tests proves very little; you must think about the worst case and the edge cases.

Judges let you pick the C++ version; most offer C++17 and C++20 and many now offer C++23. Choose the newest one available. All programs below were compiled with g++ -std=c++23 -O2 -Wall -Wextra (GCC 15), and the features that need C++17/C++20 are marked.


The Standard CP Template

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

using ll = long long;

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;
    ll sum = accumulate(a.begin(), a.end(), 0LL);   // 0LL, not 0!
    cout << sum << ' ' << *max_element(a.begin(), a.end()) << '\n';
}

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

    int t;
    cin >> t;
    while (t--) solve();
}

Input (typed or redirected from a file with ./tpl < input.txt):

3
3
1 2 3
2
1000000000 1000000000
1
-5

Output:

6 3
2000000000 1000000000
-5 -5

Line by line:

  • #include <bits/stdc++.h> — a GCC (libstdc++) internal header that includes the entire standard library. It saves typing in contests, but it is not standard C++: it does not exist with MSVC or with Apple's default Clang (which uses libc++), and it slows compilation. Use proper headers in real projects.

  • using namespace std; — normally discouraged (see Namespaces), but accepted in a single-file contest program where you control every name. Avoid naming your own variables count, distance, max etc.

  • using ll = long long; — a type alias (C++11) because you will type long long constantly.

  • The solve() function handles one test case; main reads t and calls it t times. Declaring variables inside solve() means each test starts fresh — a common bug is forgetting to reset global arrays between test cases.

  • accumulate(..., 0LL) — the type of the initial value decides the type of the sum (explained below).


Fast Input/Output

Inputs in CP can contain 105–106 numbers. With default settings, cin/cout can be several times slower than necessary, enough to cause TLE. Two lines fix it:

LineWhat it doesConsequence
ios::sync_with_stdio(false);Stops synchronizing C++ streams with C's stdio, so C++ streams get their own buffersAfter this, do not mix cin/cout with scanf/printf; output may appear out of order
cin.tie(nullptr);Unties cin from cout; by default cout is flushed before every input operationIn interactive problems you must flush yourself after each query (cout << flush or endl)
'\n' instead of endlendl = newline + flushPrinting 106 lines with endl forces 106 flushes; use '\n'

Reading patterns you will need:

  • Unknown number of values: while (cin >> x) { ... } stops at end of input.

  • Whole lines: getline(cin, s); after a cin >> n, skip the leftover newline first with cin >> ws or cin.ignore() (see Input & Output).

  • Printing with spaces but no trailing space: cout << a[i] << " \n"[i == n - 1]; — indexes the string " \n" with a bool (0 → space, 1 → newline). Most judges ignore trailing spaces anyway.


Choosing Data Types: Overflow Is the #1 WA

TypeRange (typical judge, 64-bit)Safe for
int−2 147 483 648 to 2 147 483 647 (about ±2.1 × 109)Values up to 109; never their sums or products
long longabout ±9.22 × 1018Sums of 105 values of 109; products of two numbers below about 3 × 109
unsigned long long0 to about 1.84 × 1019Hashing, bit tricks (arithmetic wraps modulo 264)
__int128about ±1.7 × 1038GCC/Clang extension for rare huge products; no cin/cout support
doubleabout 15–16 significant digitsGeometry; compare with a tolerance, never with ==

The trap: the type of an expression is decided by its operands, not by the variable you store it in. Compile with the sanitizer to see it:

#include <iostream>

int main() {
    int n = 100000;
    int bad = n * n;               // int * int overflows: undefined behavior
    long long wrong = n * n;       // still int * int, overflow happens BEFORE conversion
    long long right = 1LL * n * n; // promote first, then multiply
    std::cout << bad << '\n' << wrong << '\n' << right << '\n';
}
g++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined ovf.cpp -o ovf && ./ovf

Output:

ovf.cpp:5:9: runtime error: signed integer overflow: 100000 * 100000 cannot be represented in type 'int'
ovf.cpp:6:25: runtime error: signed integer overflow: 100000 * 100000 cannot be represented in type 'int'
1410065408
1410065408
10000000000

Signed overflow is undefined behavior; the value 1410065408 is merely what this run happened to produce (1010 mod 232), and an optimizing compiler is allowed to do anything. long long wrong = n * n; does not help, because the multiplication is done in int before the result is converted. Writing 1LL * n * n makes the first multiplication long long.

The accumulate trap

#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<long long> v(3, 2'000'000'000LL);
    std::cout << std::accumulate(v.begin(), v.end(), 0) << '\n';    // sum kept in int!
    std::cout << std::accumulate(v.begin(), v.end(), 0LL) << '\n';  // correct
}

Output:

1705032704
6000000000

std::accumulate keeps its running total in the type of the initial value. With 0 (an int) each partial sum is converted back to int and the true answer 6 000 000 000 is lost — silently, with no warning. Always write 0LL (or 0.0 for doubles).


Estimating Complexity Before You Code

A useful rule of thumb: a judge machine performs roughly 108 simple operations per second (it varies by machine and by how cache-friendly the code is). So read the constraints first and let them tell you the algorithm:

Largest nAcceptable complexity (about 1 s)Typical techniques
n ≤ 10–11O(n!)Try all permutations (next_permutation)
n ≤ 20–25O(2n · n)Subsets with bitmasks, bitmask DP
n ≤ 500O(n3)Floyd–Warshall, interval DP
n ≤ 5 000O(n2)Nested loops, 2-D DP
n ≤ 2 × 105 to 106O(n log n)Sorting, binary search, set/map, heaps, segment trees
n ≤ 107–108O(n)Prefix sums, two pointers, sieve, linear scans
n ≤ 1018O(log n) or O(√n)Binary exponentiation, binary search on the answer, math

STL operation costs you must know

Container / algorithmOperationComplexity
vectorpush_back / index / insert in middleAmortized O(1) / O(1) / O(n)
set, map (red-black tree)insert, erase, find, lower_boundO(log n)
unordered_set, unordered_mapinsert, find, eraseAverage O(1), worst case O(n)
priority_queuepush, pop / topO(log n) / O(1)
dequepush/pop at both endsO(1)
sortwhole rangeO(n log n) comparisons (guaranteed since C++11)
lower_bound, upper_bound, binary_searchon a sorted vectorO(log n)
nth_elementk-th smallestO(n) on average
strings += c / s = s + c / substr(pos, len)Amortized O(1) / O(n) (copies!) / O(len)

A classic TLE: calling std::lower_bound(s.begin(), s.end(), x) on a std::set. Set iterators are not random-access, so it takes O(n) steps to move through them. Use the member function s.lower_bound(x), which is O(log n). The same applies to map.


Sorting with Custom Comparators

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

int main() {
    // (name, marks): sort by marks descending, ties by name ascending
    vector<pair<string, int>> v{{"Ravi", 85}, {"Asha", 92}, {"Zoya", 85}, {"Dev", 70}, {"Amit", 85}};

    sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
        if (a.second != b.second) return a.second > b.second;  // strict: never true for equal
        return a.first < b.first;
    });
    for (const auto& [name, marks] : v) cout << name << ' ' << marks << '\n';

    vector<int> nums{5, 1, 4, 1, 3};
    sort(nums.begin(), nums.end(), greater<int>());              // descending
    for (int x : nums) cout << x << ' ';
    cout << '\n';
}

Output:

Asha 92
Amit 85
Ravi 85
Zoya 85
Dev 70
5 4 3 1 1 

The comparator answers "should a come before b?" and must define a strict weak ordering. In particular it must return false when the two elements are equal (comp(a, a) must be false). Using <= or >= breaks this rule and is undefined behavior — in practice it can produce wrong order, read past the end of the array, or crash on large inputs. GCC's debug mode catches it:

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

int main() {
    vector<int> v{3, 1, 2, 3, 1};
    sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });   // WRONG: not strict
    for (int x : v) cout << x << ' ';
    cout << '\n';
}
g++ -std=c++23 -D_GLIBCXX_DEBUG badcmp.cpp -o badcmp && ./badcmp

Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).

Note that std::sort is not stable: elements that compare equal may appear in any order. If the original order of ties matters, use std::stable_sort or add a tie-breaker, as we did with names.


Binary Search: Library and "On the Answer"

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

int main() {
    vector<int> a{1, 3, 3, 3, 7, 9, 12};       // must be sorted

    auto lo = lower_bound(a.begin(), a.end(), 3);   // first element >= 3
    auto hi = upper_bound(a.begin(), a.end(), 3);   // first element >  3
    cout << "first 3 at index " << (lo - a.begin()) << '\n';
    cout << "count of 3 = " << (hi - lo) << '\n';
    cout << "has 8? " << binary_search(a.begin(), a.end(), 8) << '\n';

    auto it = lower_bound(a.begin(), a.end(), 10);
    cout << "smallest >= 10: " << (it != a.end() ? *it : -1) << '\n';
    auto it2 = upper_bound(a.begin(), a.end(), 10);
    cout << "largest <= 10: " << (it2 != a.begin() ? *prev(it2) : -1) << '\n';
}

Output:

first 3 at index 1
count of 3 = 3
has 8? 0
smallest >= 10: 12
largest <= 10: 9
  a:      1   3   3   3   7   9   12
  index:  0   1   2   3   4   5   6
              ▲           ▲
        lower_bound(3)  upper_bound(3)      count = 4 - 1 = 3

lower_bound returns the first position whose element is not less than the key (≥), and upper_bound the first position whose element is greater (>). Both return end() if no such element exists, so always check before dereferencing.

Binary search on the answer

Many optimization problems ("minimize the maximum ...") have a monotonic yes/no check: if a limit L works, every larger limit works too. Then you can binary search over the answer itself. Example: books with 12, 34, 67 and 90 pages must be split, in order, between 2 students; minimize the maximum pages any student reads.

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

// Can we finish all books with each student reading at most 'limit' pages,
// using at most k students? Books are read in order (contiguous blocks).
bool feasible(const vector<ll>& pages, int k, ll limit) {
    int students = 1;
    ll current = 0;
    for (ll p : pages) {
        if (p > limit) return false;
        if (current + p > limit) { ++students; current = 0; }
        current += p;
    }
    return students <= k;
}

int main() {
    vector<ll> pages{12, 34, 67, 90};
    int k = 2;

    ll lo = 1, hi = accumulate(pages.begin(), pages.end(), 0LL);
    while (lo < hi) {                       // find the smallest feasible limit
        ll mid = lo + (hi - lo) / 2;
        if (feasible(pages, k, mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << "minimum maximum pages = " << lo << '\n';
}

Output:

minimum maximum pages = 113

The best split is [12, 34, 67] = 113 and [90]. Each check is O(n) and there are O(log(sum)) checks, so the total is O(n log(sum)). Note mid = lo + (hi - lo) / 2, which cannot overflow, unlike (lo + hi) / 2 near the top of the range.


Prefix Sums: O(1) Range Queries

For an array a[1..n], the prefix sum array is pre[0] = 0 and pre[i] = pre[i−1] + a[i]. The sum of a[l..r] is then pre[r] − pre[l−1], computed in O(1) after O(n) preprocessing.

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

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

    int n, q;
    cin >> n >> q;
    vector<ll> pre(n + 1, 0);              // pre[i] = a[1] + ... + a[i]
    for (int i = 1; i <= n; ++i) {
        ll x;
        cin >> x;
        pre[i] = pre[i - 1] + x;
    }
    while (q--) {
        int l, r;                          // 1-based, inclusive
        cin >> l >> r;
        cout << pre[r] - pre[l - 1] << '\n';
    }
}

Input:

6 3
4 -2 7 1 5 3
1 3
2 5
4 4

Output:

9
11
1

Answering q queries by looping over each range would be O(n · q) — up to 1010 operations for n = q = 105. With prefix sums it is O(n + q).


Modular Arithmetic

When the answer is huge, problems ask for it "modulo 109 + 7". This number is prime, and (109 + 6)2 ≈ 1018 still fits in a long long, so you can multiply two reduced values safely before taking % again.

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

const ll MOD = 1'000'000'007;              // a prime

ll power(ll base, ll exp, ll mod) {        // binary exponentiation: O(log exp)
    ll result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    cout << power(2, 10, MOD) << '\n';
    cout << power(2, 1'000'000'000'000LL, MOD) << '\n';

    ll inv3 = power(3, MOD - 2, MOD);      // Fermat: a^(p-2) is the inverse of a mod p
    cout << inv3 << ' ' << (3 * inv3) % MOD << '\n';

    ll a = 5, b = 8;
    cout << ((a - b) % MOD + MOD) % MOD << '\n';   // safe subtraction under modulo
}

Output:

1024
959366170
333333336 1
1000000004
  • Binary exponentiation computes ab in O(log b) by squaring: 21012 needs only about 40 iterations.

  • Modular inverse: for a prime p and a not divisible by p, Fermat's little theorem gives ap−2 ≡ a−1 (mod p). Use it to "divide" under a modulus, e.g. for nCr.

  • Negative remainders: in C++, % keeps the sign of the left operand, so (5 - 8) % MOD is −3. Add MOD and reduce again.

  • Reduce after every operation; (a * b * c) % MOD can overflow even if each value is reduced.


Bit Manipulation

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

int main() {
    unsigned x = 0b1011'0100;                        // 180
    cout << popcount(x) << ' '                       // C++20 <bit>: number of 1 bits
         << __builtin_popcount(x) << ' '             // GCC built-in, same answer
         << countr_zero(x) << ' '                    // trailing zeros (C++20)
         << bit_width(x) << '\n';                    // floor(log2 x) + 1 (C++20)

    int n = 12;
    cout << ((n & (n - 1)) == 0 ? "power of 2" : "not a power of 2") << '\n';
    cout << "lowest set bit: " << (n & -n) << '\n';

    // enumerate all subsets of {a, b, c}
    string items = "abc";
    int k = items.size();
    for (int mask = 0; mask < (1 << k); ++mask) {
        cout << '{';
        for (int i = 0; i < k; ++i)
            if (mask >> i & 1) cout << items[i];
        cout << "} ";
    }
    cout << '\n';
}

Output:

4 4 2 8
not a power of 2
lowest set bit: 4
{} {a} {b} {ab} {c} {ac} {bc} {abc} 

The C++20 header <bit> gives portable std::popcount, std::countr_zero, std::countl_zero, std::bit_width and std::has_single_bit; they accept only unsigned types. The GCC built-ins (__builtin_popcount, __builtin_popcountll for 64-bit, __builtin_ctz, __builtin_clz) are common in older code; note that __builtin_ctz(0) and __builtin_clz(0) are undefined. Also remember that 1 << 40 overflows an int; write 1LL << 40.


Graphs: Dijkstra with a Min-Heap

Graph problems combine several STL pieces: an adjacency list (vector<vector<pair>>), a priority_queue turned into a min-heap with greater<> (see stack, queue & priority_queue), and structured bindings (C++17).

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

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

    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, ll>>> adj(n + 1);         // adj[u] = {(v, w), ...}
    for (int i = 0; i < m; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    const ll INF = LLONG_MAX;
    vector<ll> dist(n + 1, INF);
    // min-heap of (distance, vertex)
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    dist[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) continue;                   // stale entry, skip
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    for (int v = 1; v <= n; ++v)
        cout << (dist[v] == INF ? -1 : dist[v]) << " \n"[v == n];
}

Input (5 vertices, 6 undirected weighted edges):

5 6
1 2 4
1 3 1
3 2 2
2 4 5
3 4 8
4 5 3

Output (shortest distance from vertex 1 to each vertex):

0 3 1 8 11

Instead of a "decrease-key" operation, which priority_queue does not have, we push a new pair and skip outdated ones with if (d != dist[u]) continue;. The complexity is O((n + m) log m). Distances use long long because a path of 105 edges of weight 109 exceeds int.


Hashing Safely: Anti-Hash Tests

unordered_map is O(1) only on average. libstdc++ hashes an integer to itself and uses a predictable sequence of prime bucket counts, so on open-hacking platforms like Codeforces, people craft inputs where every key lands in the same bucket, turning each operation into O(n) and your solution into TLE. Two defenses:

  1. Use map (guaranteed O(log n)) when its speed is enough.

  2. Give unordered_map a randomized hash function:

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

struct SafeHash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t seed =
            chrono::steady_clock::now().time_since_epoch().count();   // differs per run
        return splitmix64(x + seed);
    }
};

int main() {
    unordered_map<long long, int, SafeHash> freq;
    freq.reserve(1 << 10);
    for (long long x : {5LL, 7LL, 5LL, 1'000'000'000'000LL, 5LL}) ++freq[x];
    cout << freq[5] << ' ' << freq[7] << ' ' << freq[1'000'000'000'000LL] << '\n';
}

Output:

3 1 1

splitmix64 scrambles the bits thoroughly, and adding a seed taken from the clock means the hacker cannot predict the bucket of a key. reserve pre-allocates buckets so the table does not repeatedly rehash as it grows.


Debugging Like a Pro

Tool / flagWhat it catches
-Wall -Wextra -Wshadow -WconversionUnused variables, shadowed names, lossy conversions such as int x = someLongLong;
-fsanitize=address,undefinedOut-of-bounds access, use after free, signed overflow, invalid shifts
-D_GLIBCXX_DEBUGlibstdc++ debug mode: out-of-range vector indexing, invalid iterators, bad comparators
cerr for debug printsMost judges ignore standard error, but leftover prints still cost time — remove them before submitting
Brute-force checkerWrite a slow, obviously-correct solution and compare outputs on many small random tests

Compile locally with sanitizers and debug mode, but submit without them: they make the program several times slower.


Common Mistakes

  • int where long long is needed — sums, products, distances, answers that "can be large".

  • accumulate(v.begin(), v.end(), 0) on large values — use 0LL.

  • endl in a loop printing 106 lines — flushes every time; use '\n'.

  • Mixing scanf/printf with cin/cout after sync_with_stdio(false).

  • v.size() - 1 when v is empty — size() is unsigned, so the result wraps to a huge number. Cast to int first or check emptiness.

  • Comparator with <= — undefined behavior in sort, set and map.

  • std::lower_bound on a set/map — O(n); use the member function.

  • Large local arrays like int a[1000000]; inside a function can overflow the stack (limits differ between judges); make them global, static, or a vector. Global arrays are also zero-initialized automatically.

  • Not resetting data between test cases — global arrays and containers keep values from the previous test.

  • memset(a, 1, sizeof a) to fill an int array with 1 — memset sets bytes, giving 16843009; only 0 and −1 work this way. Use fill or vector's constructor.

  • Very deep recursion (DFS on a 106-node path) — may overflow the stack; use an explicit stack if the judge's stack is small.

  • Comparing double with == — use fabs(a - b) < 1e-9.


Interview / GATE-Style Questions

Q1. What do ios::sync_with_stdio(false) and cin.tie(nullptr) do, and when can they cause bugs?

The first disables synchronization between C++ streams and C stdio, letting cin/cout use their own fast buffers; mixing them with scanf/printf afterwards can reorder input or output. The second stops cout from being flushed before each read from cin; in interactive problems you must then flush explicitly after every query, or the judge never sees it.

Q2. int n = 100000; long long x = n * n; — what is x?

The behavior is undefined: n * n is computed in int and overflows before the conversion to long long. On typical machines you see 1410065408, but nothing is guaranteed. Write 1LL * n * n or make n a long long.

Q3. n ≤ 2 × 105 and the time limit is 1 second. Is an O(n2) algorithm acceptable?

No. 4 × 1010 operations is hundreds of times more than about 108 per second. You need O(n log n) or O(n).

Q4. Why should a comparator passed to std::sort never use <=?

std::sort requires a strict weak ordering, which includes irreflexivity: comp(a, a) must be false. With <=, equal elements compare "less" both ways, which violates the precondition. The result is undefined behavior: wrong order, out-of-bounds reads or a crash.

Q5. How do you count occurrences of x in a sorted vector in O(log n)?

upper_bound(v.begin(), v.end(), x) - lower_bound(v.begin(), v.end(), x), which is the distance between the first element > x and the first element ≥ x.

Q6. Why is 109 + 7 such a popular modulus?

It is prime, so every nonzero value has a modular inverse (via Fermat's little theorem), and it is just under 230, so the sum of two reduced values fits in int and the product of two reduced values (below about 1018) fits in a 64-bit long long.

Q7. Can unordered_map be slower than map?

Yes. Its average cost is O(1), but with many collisions (for example, deliberately crafted anti-hash inputs) operations degrade to O(n), and rehashing plus poor cache behavior adds constant factors. map guarantees O(log n). A randomized custom hash and reserve make unordered_map safe and fast.


Summary

  • Start from a template: solve() per test case, fast I/O (sync_with_stdio(false), cin.tie(nullptr)), and '\n' instead of endl.

  • <bits/stdc++.h> and using namespace std; are contest conveniences, not good practice in real projects.

  • Use long long for sums, products and answers; promote before multiplying (1LL * a * b); start accumulate with 0LL.

  • Read the constraints and estimate complexity using about 108 simple operations per second.

  • Know STL costs: set/map O(log n), unordered containers O(1) average but O(n) worst, sort O(n log n); use member lower_bound on sets and maps.

  • Core patterns: custom comparators (strict!), lower_bound/upper_bound, binary search on the answer, prefix sums, modular exponentiation and inverse, bitmasks, Dijkstra with a min-heap.

  • Debug locally with -Wall -Wextra, -fsanitize=address,undefined and -D_GLIBCXX_DEBUG; submit without them.