• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Apr 26th, 2019 112 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /**
2.     Complexitate O(n log n + T log n)
3. */
4. #include <bits/stdc++.h>
5. #define nmax 200003
6. using namespace std;
7.
8. int a[nmax], n;
9.
10. /// cauta binar cea mai din stanga pozitie p
11. /// cu proprietatea ca x <= a[p]
12. int CautBin1(int x)
13. {
14.     if (a[n] < x) return n + 1;
15.     if (x <= a[1]) return 1;
16.     int st, dr, m, p;
17.     st = 1; dr = n; p = 1;
18.     while (st <= dr)
19.     {
20.         m = (st + dr) / 2;
21.         if (x <= a[m])
22.         {
23.             p = m; dr = m - 1;
24.         }
25.         else st = m + 1;
26.     }
27.     return p;
28. }
29.
30. /// cauta binar cea mai din dreapta pozitie p
31. /// cu proprietatea ca a[p] <= y
32. int CautBin2(int y)
33. {
34.     if (a[n] <= y) return n;
35.     if (a[1] > y) return 0;
36.     int st, dr, m, p;
37.     st = 1; dr = n; p = 1;
38.     while (st <= dr)
39.     {
40.         m = (st + dr) / 2;
41.         if (a[m] <= y)
42.         {
43.             p = m; st = m + 1;
44.         }
45.         else dr = m - 1;
46.     }
47.     return p;
48. }
49.
50. int main()
51. {
52.     int i, p, q, T, x, y;
53.     cin >> n >> T;
54.     for (i = 1; i <= n; i++)
55.         cin >> a[i];
56.
57.     sort(a + 1, a + n + 1);
58.
59.     while (T--)
60.     {
61.         cin >> x >> y;
62.         p = CautBin1(x);
63.         q = CautBin2(y);
64.         cout << (q - p + 1) << "\n";
65.     }
66.
67.     return 0;
68. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top