You are viewing a single comment's thread. Return to all comments →
#include <bits/stdc++.h> using namespace std; using FastCounter = std::array<int, 205>; double get_median_fast(const FastCounter& counter, int, int) { FastCounter partial_sum; std::partial_sum(counter.begin(), counter.end(), partial_sum.begin()); const auto total_elems = partial_sum.back(); if (const bool odd = partial_sum.back() & 0x1; odd) { int mid_cnt = total_elems + 1; auto lb = std::lower_bound(partial_sum.begin(), partial_sum.end(), mid_cnt); return static_cast<double>(lb - partial_sum.begin()); } else { int left_cnt = total_elems, right_cnt = left_cnt + 1; const auto l = std::lower_bound(partial_sum.begin(), partial_sum.end(), left_cnt); const auto r = std::lower_bound(l, partial_sum.end(), right_cnt); const double lc = l - partial_sum.begin(); const double rc = r - partial_sum.begin(); return (lc+rc) / 2.0; } } void update_fast(FastCounter& c, int remove, int add) { c[remove]--; c[add]++; } int activityNotifications(vector<int>& nums, int window) { int notify = 0; FastCounter counter = {0}; for (auto head = nums.begin(); head != nums.begin()+window; ++head) { counter[*head]++; } for (auto add = nums.begin()+window; add != nums.end(); ++add) { int idx = window / 2 + 1; auto median = get_median_fast(counter, window, window & 0x1); if (*add >= 2 * median) { notify++; } update_fast(counter, *(add-window), *add); } return notify; }
Seems like cookies are disabled on this browser, please enable them to open this website
Fraudulent Activity Notifications
You are viewing a single comment's thread. Return to all comments →