CP Shots

upper_bound in C++

upper_bound() is a standard library function in C++ defined in the header. It returns an iterator pointing to the first element in the range [first, last] that is greater than value, or last if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to val. Classic example - https://codeforces.com/problemset/problem/706/B

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> prices(n);
    for (int i = 0; i < n; i++) {
        cin >> prices[i];
    }
    sort(prices.begin(), prices.end());
    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;
        int res = upper_bound(prices.begin(), prices.end(), x) - prices.begin();
        cout << res << "\n";
    }
    return 0;
}

Find a value in a vector.

// x is the item we are finding in arr vector
auto it = find(arr.begin(), arr.end(), x);
if (it != arr.end()) {
    cout << "we found!";
}

Get substring from a string

string str = "Hello World!";
string tmp = str.substring(0, 5); // first value is index, second is length

Find a substring inside a string

string str = "Hello World!";
string strToFind = "Hello";
auto found = str.find(strToFind);
if (found != string::npos) {
    cout << "Index where the strToFind start is : " << found << endl;
}

⭐ Fast I/O in CPP

Add below lines after your int main() line :

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

Set precision according to question constraints

Add below lines after int main() line :

    cout.precision(10);
    cout.setf(ios::fixed);

Pointers

1. Try using const in modulo operations, since Modulo operations are very fast with constant mod (because compiler notices constant, and so instead of actually dividing, replaces it with a sequence of faster bitwise operations) A trivial example would be % 2 being replaced by ^ 1.

   const long long mod = 1e9 + 7;

2. Bitwise : https://codeforces.com/blog/entry/72437

3. memset function is for char or 1 byte data types only. So memset(a, 1, sizeof(a)) won't work 🥷https://www.geeksforgeeks.org/memset-in-cpp/

4. Use \n over endl : https://www.geeksforgeeks.org/endl-vs-n-in-cpp/