Description

Submission

• Counting sort
• O(200N)
• When d is even and d/2, d/2+1 lies in the middle is a special case

#include <vector>
#include <iostream>

using namespace std;

// Complete the activityNotifications function below.
int activityNotifications(vector<int> expenditure, int d) {
    vector<int> count(201);

    for(int i = 0; i < 201; ++i) {
        count[i] = 0;
    }

    int nNotifications = 0;
    for(int i = 0; i < d; ++i) {
        count[expenditure[i]]++;
    }

    for(int i = d; i < expenditure.size(); ++i) {
        // find the median * 2
        int s = 0;
        int m = 0;
        for(int j = 0; j < count.size(); ++j) {
            s += count[j];
            if(s * 2 > d) {
                m = j * 2;
                break;
            }
            if(s * 2 == d) {
                for(int k = j + 1; k < d; ++k) {
                    if(count[k] != 0) {
                        m = k + j;
                        break;
                    }
                }
                break;
            }
        }

        if(expenditure[i]  >= m) nNotifications++;

        count[expenditure[i - d]]--;
        if(i + 1 != expenditure.size()) count[expenditure[i]]++;
    }
    return nNotifications;
}

int main()
{
    int n, d; cin >> n >> d;

    vector<int> expenditure(n);

    for (int i = 0; i < n; i++) {
        cin >> expenditure[i];
    }

    int result = activityNotifications(expenditure, d);

    cout << result << "\n";

    return 0;
}