left and right intervals

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
737 B
21
Indexable
Never
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    int a[n];
    
    // a[0] ... a[n-1]
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    // O(K*log2_N)
    for (int i = 0; i < k; ++i) {
        int x;
        cin >> x;
        // a[j - 1] < x <= a[j] -> lower_bound
        // a[j - 1] <= x < a[j] -> upper_bound
        
        int j = (lower_bound(a + 0, a + n, x) - a);
        if (j == n || a[j] > x) {
            cout << 0 << endl;
        } else {
            int l = j + 1;
            int r = ((upper_bound(a + 0, a + n, x) - a) - 1) + 1;
            cout << l << ' ' << r << endl;
        }
    }

    return 0;
}

// N -> N/2 -> N/4 -> N/8 ... 1