C++ for DSA and Competitive Programming

Speed, STL and avoiding traps

C++ dominates competitive programming because it is fast and its STL provides most data structures you need. Useful habits: speed up I/O with std::ios::sync_with_stdio(false); std::cin.tie(nullptr);; use long long whenever values can exceed about 2 × 10⁹, since signed overflow is undefined; know your containers' costs (vector, deque, set, map, unordered_map, priority_queue); use std::sort with lambdas, lower_bound/upper_bound for binary search on sorted data, and std::accumulate carefully (its initial value's type determines the accumulation type, so use 0LL for large sums). Watch for unordered_map performance attacks in contests with adversarial tests; a custom hash or map avoids them. Avoid #include <bits/stdc++.h> and using namespace std; in real projects, even though they are common in contests, because they are non-standard or pollute names. Recursion depth can overflow the stack for deep DFS on large graphs; use iterative versions when n is large.

A contest-style template

Fast I/O, long long sums, sorting with a comparator and binary search.

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

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

    int n;
    std::cin >> n;
    std::vector<long long> a(n);
    for (auto& x : a) std::cin >> x;

    long long total = std::accumulate(a.begin(), a.end(), 0LL);   // 0LL, not 0: avoid int overflow

    std::sort(a.begin(), a.end());
    long long query = 42;
    auto it = std::lower_bound(a.begin(), a.end(), query);       // first element >= query
    std::size_t count_less = static_cast<std::size_t>(it - a.begin());

    std::vector<std::pair<int, int>> intervals{{3, 5}, {1, 4}, {2, 2}};
    std::sort(intervals.begin(), intervals.end(),
              [](const auto& x, const auto& y) { return x.second < y.second; });   // by end time

    std::cout << total << ' ' << count_less << '\n';            // '\n' instead of std::endl (no flush)
}

A well-stocked toolbox

In a contest, the STL is a toolbox already in your bag: sorted sets, heaps, binary search, hash maps. Knowing exactly which tool to grab, and its cost, wins more than writing your own from scratch.

Quick check: Why use `std::accumulate(a.begin(), a.end(), 0LL)` instead of `0` for a large sum of long long values?

• 0LL is faster to type
• The initial value's type sets the accumulator type; 0 would accumulate in int and could overflow
• accumulate requires 0LL
• It sorts the vector first