Upper bound

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 22e4;
 
int a[N], t[N];
int cal(int n) {
    int ans = 1;
    for (int i = 0, l = -1, mx = 0; i < n; i++) {
        mx = max(mx, a[i]);
        if (t[i - l] < mx)l = i - 1, ans++, mx = a[i];
        if (t[1] < a[i])return -1;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    int T=1, n, m;
    
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            t[i + 1] = 0;
        }
        cin >> m;
        for (int i = 0, x, y; i < m; i++) {
            cin >> x >> y;
            t[y] = max(t[y], x);
        }
        for (int i = n - 1; i > 0; i--) {
            t[i] = max(t[i], t[i + 1]);
        }
        cout << cal(n) << '\n';
    }
    return 0;
}

#include <iostream>
#include <vector>
 
namespace my
{
    template<class ForwardIt, class T>
    ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value)
    {   ForwardIt it;
        typename std::iterator_traits<ForwardIt>::difference_type count, step;
        count = std::distance(first, last);
 
        while (count > 0)
        {   it = first;
            step = count / 2;
            std::advance(it, step);
            if (!(value < *it))
            {   first = ++it;
                count -= step + 1;
            }
            else
                count = step;
        }
        return first;
    }
};
 
int main()
{   ///-----------------------------------------------|
    /// Для работы с upper_bound                      |
    /// data должно быть остортированно!              |
    ///-----------------------------------------------:
    const std::vector<int> data = { 1, 2, 4, 5, 5, 6 };
    for (int i = 0; i < 7; ++i)
    {   auto upper = my::upper_bound(data.begin(), data.end(), i);
 
        std::cout << i << ": " << upper - data.begin() << '\n';
    }
}

{   ///-----------------------------------------------|
    /// Для работы с upper_bound                      |
    /// data должно быть отсортировано!               |
    ///-----------------------------------------------:

#include <iostream>
#include <vector>
#include <algorithm>
 
namespace my
{
    template<class ForwardIt, class T>
    ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value)
    {   ForwardIt it;
        typename std::iterator_traits<ForwardIt>::difference_type count, step;
        count = std::distance(first, last);
 
        while (count > 0)
        {   it = first;
            step = count / 2;
            std::advance(it, step);
            if (!(value < *it))
            {   first = ++it;
                count -= step + 1;
            }
            else
                count = step;
        }
        return first;
    }
};
 
int main()
{
    int n; std::cin >> n;
    std::vector<int> data(n);
    for(auto& e : data) std::cin >> e;
 
    std::sort(data.begin(), data.end());
 
    std::cin >> n;
 
    for (int i = 0, nn = n-1; i < n; ++i)
    {   int a; std::cin >> a;
        auto upper = my::upper_bound(data.begin(), data.end(), a);
 
        std::cout << upper - data.begin();
        if(i != nn) std::cout << ' '; /// вывод в строчку и проверка чтобы не печатался последний пробел в строке.
    }
}

#include <iostream>
#include <vector>
#include <algorithm>
 
int main()
{   int n;
    std::cin >> n;
    std::vector<int> data(n);
    for(auto& e : data) std::cin >> e;
 
    std::sort(data.begin(), data.end());
 
    std::cin >> n;
 
    for (int i = 0, nn = n-1; i < n; ++i)
    {   int value;
        std::cin >> value;
 
        auto first(data.begin());
        {   auto it   (data.begin());
            auto last (data.end  ());
 
            typename std::iterator_traits<std::vector<int>::iterator>::
                                                    difference_type count, step;
            count = std::distance(first, last);
 
            while (count > 0)
            {   it = first;
                step = count / 2;
                std::advance(it, step);
                if (!(value < *it))
                {   first = ++it;
                    count -= step + 1;
                }
                else
                    count = step;
            }
        }
 
        std::cout << first - data.begin();
        if(i != nn) std::cout << ' ';
    }
}

#include <iostream>
 
int main() 
{
  const unsigned MIN = -109, MAX = 109, TOTAL = MAX - MIN + 1;
  unsigned counts[TOTAL] = { 0 };
   
  unsigned n = 0;
  std::cin >> n;
   
  for (; n > 0; --n)
  {
    int v = 0;
    std::cin >> v;
    ++counts[v - MIN];
  }
 
  for (unsigned i = 1; i < TOTAL; ++i)
    counts[i] += counts[i - 1];
 
  unsigned m = 0;
  std::cin >> m;
 
  for (; m > 0; --m)
  {
    int v = 0;
    std::cin >> v;
    std::cout << counts[v - MIN] << " ";
  }
 
  std::cout << std::endl;
}

#include <iostream>
#include <vector>
#include <algorithm>
 
int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    std::sort(a.begin(), a.end());
    
    int M;
    std::cin >> M;
    std::vector<int> b(M);
    for (int i = 0; i < M; ++i) {
        std::cin >> b[i];
    }
    
    std::vector<int> answers;
    for (int x : b) {
        int L = -1;
        int R = n;
        while (R - L > 1) {
            int mid = (R + L) / 2;
            if (a[mid] > x) {
                R = mid;
            } else {
                L = mid;
            }
        }
        answers.push_back(R);
    }
    
    for (int answer : answers) {
        std::cout << answer << " ";
    }
    std::cout << std::endl;
 
    return 0;
}