Upiti intervala

Dat je niz celih brojeva. Za svaki od upita oblika \(a\ b\) ispisati najmanji i najveći broj iz intervala \([a, b]\) koji pripada nizu.

Opis ulaza

Sa standardnog ulaza se učitava veličina niza \(n\) (\(1 \leq n \leq 10^6\)), a zatim i \(n\) elemenata niza. Nakon toga se učitava broj \(k\) (\(1 \leq k \leq 10^4\)), a zatim i \(k\) upita oblika \(a\ b\).

Opis izlaza

Za svaki od upita na standardni izlaz ispisati najmanji i najveći broj iz datog intervala koji pripada nizu. Ukoliko intervalu pripada samo jedan broj iz niza, ispisati njega dvaput. Ukoliko intervalu ne pripada ni jedan broj iz niza, ispisati NEMA.

Primer

Ulaz

Izlaz

Rešenje

Opis glavnog rešenja

U ovom bloku se opisuje glavno rešenje zadatka.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() 
{
    int n; cin >> n;

    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    sort(v.begin(), v.end());

    int k; cin >> k;

    while (k--) {
        int a, b; cin >> a >> b;

        auto it_min = lower_bound(v.begin(), v.end(), a);
        auto it_max = upper_bound(v.begin(), v.end(), b) - 1;

        if (it_max < it_min){
            cout << "NEMA" << endl;
        } else {
            cout << *it_min << " " << *it_max << endl;
        }
    }

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

int main() 
{
    int n; cin >> n;

    vector<int> v(n);
    for(int i = 0; i < n; i++) {
        cin >> v[i];
    }

    int k; cin >> k;

    while (k--) {
        int a, b; cin >> a >> b;

        int m = numeric_limits<int>::max(), M = numeric_limits<int>::min();
        for (int i = 0; i < n; i++) {
            if (a <= v[i] && v[i] <= b) {
                m = min(m, v[i]);
                M = max(M, v[i]);
            }
        }

        if (m != numeric_limits<int>::max() && M != numeric_limits<int>::min()) {
            cout << m << " " << M << endl;
        } else {
            cout << "NEMA" << endl;
        }
    }

    return 0;
}