Hamoudi30

Untitled

Dec 11th, 2021 (edited)
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.28 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int last (int a[], int n, int x) {
  4.     int st = 0, ed = n - 1;
  5.     int found = -1;
  6.     while (st <= ed) {
  7.         int mid = (st + ed) / 2;
  8.         if (a[mid] > x) {
  9.             ed = mid - 1;
  10.         } else if (a[mid] < x) {
  11.             st = mid + 1;
  12.         } else {
  13.             // a[mid] == x
  14. //            found
  15.             found = mid;
  16.             // last
  17.             st = mid + 1;
  18.         }
  19.     }
  20.     return found;
  21.     // log(N)
  22. }
  23. int first (int a[], int n, int x) {
  24.     int st = 0, ed = n - 1;
  25.     int found = -1;
  26.     while (st <= ed) {
  27.         int mid = (st + ed) / 2;
  28.         if (a[mid] > x) {
  29.             ed = mid - 1;
  30.         } else if (a[mid] < x) {
  31.             st = mid + 1;
  32.         } else {
  33.             // a[mid] == x
  34. //            found
  35.             found = mid;
  36.             // first
  37.             ed = mid - 1;
  38.         }
  39.     }
  40.     return found;
  41.     // log(N)
  42. }
  43. const int N = 2e5+9;
  44. int a[N];
  45. int main() {
  46.     int n;
  47.     cin >> n;
  48.     for (int i = 0; i < n; ++i)
  49.         cin >> a[i];
  50.     sort(a, a + n); // O(NlogN)
  51.     int x;
  52.     cin >> x;
  53.     int st = first(a, n, x);
  54.     int ed = last(a, n, x);
  55.     if (st == -1)
  56.         cout << "not";
  57.     else
  58.         cout << ed - st + 1 << '\n';
  59.     return 0;
  60. }
Add Comment
Please, Sign In to add comment