C++¶

Please read (at least) the following parts of Competitive Programmer’s Handbook:

Section 1.1: Programming languages
Section 1.2: Input and output (note std::ios::sync_with_stdio)
Section 1.3: Working with numbers (note long long)
Section 1.4: Shortening code
Section 3.2: Sorting in C++
Section 4.5: Other structures: Bitset (note std::bitset)
Section 10.1: Bit representation
Section 10.2: Bit operations (note __builtin_popcount etc.)
Section 10.3: Representing sets
Section 10.4: Bit optimizations

What can I do in one second?¶

Modern C++ compilers produce very efficient machine code, and modern CPUs are very fast.

You can expect to do more than 1 billion elementary arithmetic operations (addition, subtraction, multiplication, and bit manipulation for integers or floating-point numbers) in less than 1 second. Just keep in mind that divisions are much slower than multiplications.

Arrays are great for performance, especially if the arrays are small (fit in caches) or if you do linear reading and writing. With small arrays, you can expect to do hundreds of millions of array updates in less than 1 second.

Sorting with std::sort is also surprisingly fast; you can expect to be able to sort an array with 10 million elements in less than 1 second. Following a linked list can be as slow as sorting.

Do not expect to be able to do much more than some millions of updates in hash tables (e.g. std::unordered_set and std::unordered_map) per second. Tree-like data structures (e.g. std::set and std::map) are even worse.

You can easily read and write millions of numbers per second, but only if you use std::ios_base::sync_with_stdio(0).