Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int last (int a[], int n, int x) {
- int st = 0, ed = n - 1;
- int found = -1;
- while (st <= ed) {
- int mid = (st + ed) / 2;
- if (a[mid] > x) {
- ed = mid - 1;
- } else if (a[mid] < x) {
- st = mid + 1;
- } else {
- // a[mid] == x
- // found
- found = mid;
- // last
- st = mid + 1;
- }
- }
- return found;
- // log(N)
- }
- int first (int a[], int n, int x) {
- int st = 0, ed = n - 1;
- int found = -1;
- while (st <= ed) {
- int mid = (st + ed) / 2;
- if (a[mid] > x) {
- ed = mid - 1;
- } else if (a[mid] < x) {
- st = mid + 1;
- } else {
- // a[mid] == x
- // found
- found = mid;
- // first
- ed = mid - 1;
- }
- }
- return found;
- // log(N)
- }
- const int N = 2e5+9;
- int a[N];
- int main() {
- int n;
- cin >> n;
- for (int i = 0; i < n; ++i)
- cin >> a[i];
- sort(a, a + n); // O(NlogN)
- int x;
- cin >> x;
- int st = first(a, n, x);
- int ed = last(a, n, x);
- if (st == -1)
- cout << "not";
- else
- cout << ed - st + 1 << '\n';
- return 0;
- }
Add Comment
Please, Sign In to add comment