0

I had a task to find if multiple numbers (n) are in multiple intervals (m) and I was pointed to lower_bound and upper_bound to do the checking faster than O(nm) , something like O((n+m)*log(n)). 

#include <bits/stdc++.h>
using namespace std;


int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    int n, m, temp, temp1;
    vector <pair<int, int>> uogienes;
    vector <int> erskeciai;

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        erskeciai.push_back(temp);
    }
    temp = 0;
    for (int i = 0; i < m; i++) {
        cin >> temp >> temp1;
        uogienes.push_back(make_pair(temp, temp1));
    }
    for (int i = 0; i < m; i++) {
        temp = 0;
        for (int h = 0; h < n; h++) {
            if (uogienes[i].first <= erskeciai[h] && uogienes[i].second >= erskeciai[h]) {
                temp++;
            }
        }
        cout << temp << "\n";
    }
    return 0;
}

Now I have no idea how to progress further with lower_bound or upper_bound, since they are pretty new to me, so are iterators etc. Could anyone help me with this task?

J. Doe
  • 45
  • 7
  • 1
    If iterators is new to you, then you should probably start with [a good beginners book or two](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) first, before you move on to [`std::lower_bound`](http://en.cppreference.com/w/cpp/algorithm/lower_bound) and [`std::upper_bound`](http://en.cppreference.com/w/cpp/algorithm/upper_bound). – Some programmer dude Jan 06 '18 at 15:21
  • boost::icl could also help. – Marc Glisse Jan 06 '18 at 15:27
  • I'll give a hint. You have to look at every number, every time. But what if you sorted erskeciai? – Kenny Ostrom Jan 06 '18 at 16:05
  • 1
    ps: don't use "bits/stdc++.h" https://stackoverflow.com/search?q=bits%2Fstdc%2B%2B.h , avoid "using namespace std" although it's okay on small programs, https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice – Kenny Ostrom Jan 06 '18 at 16:08

0 Answers0