left and right intervals
unknown
c_cpp
3 years ago
737 B
24
Indexable
#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
Editor is loading...