# C++ for DSA and Competitive Programming — C++

Source: https://www.skillbyai.com/en/cpp/p-competitive

> Write fast, correct C++ for coding interviews and contests.

## 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.

```cpp
#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.

**Quiz:** 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
- [x] 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

*Answer:* The initial value's type sets the accumulator type; 0 would accumulate in int and could overflow. accumulate returns and accumulates in the type of the initial value.