Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- Complexitate O(n log n + T log n)
- */
- #include <bits/stdc++.h>
- #define nmax 200003
- using namespace std;
- int a[nmax], n;
- /// cauta binar cea mai din stanga pozitie p
- /// cu proprietatea ca x <= a[p]
- int CautBin1(int x)
- {
- if (a[n] < x) return n + 1;
- if (x <= a[1]) return 1;
- int st, dr, m, p;
- st = 1; dr = n; p = 1;
- while (st <= dr)
- {
- m = (st + dr) / 2;
- if (x <= a[m])
- {
- p = m; dr = m - 1;
- }
- else st = m + 1;
- }
- return p;
- }
- /// cauta binar cea mai din dreapta pozitie p
- /// cu proprietatea ca a[p] <= y
- int CautBin2(int y)
- {
- if (a[n] <= y) return n;
- if (a[1] > y) return 0;
- int st, dr, m, p;
- st = 1; dr = n; p = 1;
- while (st <= dr)
- {
- m = (st + dr) / 2;
- if (a[m] <= y)
- {
- p = m; st = m + 1;
- }
- else dr = m - 1;
- }
- return p;
- }
- int main()
- {
- int i, p, q, T, x, y;
- cin >> n >> T;
- for (i = 1; i <= n; i++)
- cin >> a[i];
- sort(a + 1, a + n + 1);
- while (T--)
- {
- cin >> x >> y;
- p = CautBin1(x);
- q = CautBin2(y);
- cout << (q - p + 1) << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement