Code : Kill Monsters (Hard Version)

#include <bits/stdc++.h>
using namespace std;

void solve(vector<long long> &a, long long x, long long k) {
    int n = a.size();

    map<int, int> freq;
    for (int i = 0; i < n; i++) {
        freq[a[i]]++;
        freq[a[i]] = min(freq[a[i]], 2);
    }

    n = freq.size();
    vector<int> alive(n);

    a.clear();
    int idx = 0;
    for (auto &[key, val] : freq) {
        a.push_back(key);
        alive[idx++] = val;
    }

    int ans = 0;
    // Apply the operation right now.
    int unsafe = lower_bound(a.begin(), a.end(), x * k) - a.begin();
    ans = unsafe;

    unsafe = lower_bound(a.begin(), a.end(), x) - a.begin();
    for (int i = unsafe; i < n; i++) {
        alive[i] = min(alive[i], 1);
    }

    int taken = 0;
    for (int now = unsafe - 1; now >= 0; now--) {
        taken++;
        alive[now]--;

        // Now, do the operation.
        unsafe = lower_bound(a.begin(), a.end(), a[now] * k) - a.begin();

        int remain = 0;
        for (int i = now; i < unsafe; i++) {
            remain += alive[i];
        }
        ans = max(ans, taken + now + remain);
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        int n;
        long long x, k;
        cin >> n >> x >> k;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a, x, k);
    }
    return 0;
}

#include <atcoder/segtree>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

int op(int a, int b) { return a + b; }

int e() { return 0; }

class BlackBox {
  public:
    segtree<int, op, e> *st;
    BlackBox(int n) { st = new segtree<int, op, e>(n); }

    int range_sum(int l, int r) {
        if (l > r) {
            return 0;
        }
        return st->prod(l, r + 1);
    }

    int get(int i) { return range_sum(i, i); }

    void add(int idx, int delta) {
        int current = get(idx);
        st->set(idx, current + delta);
    }

    void set(int idx, int new_val) { st->set(idx, new_val); }
};

void solve(vector<long long> &a, long long x, long long k) {
    int n = a.size();

    map<long long, int> freq;
    for (int i = 0; i < n; i++) {
        freq[a[i]]++;
        freq[a[i]] = min(freq[a[i]], 2);
    }

    n = freq.size();
    BlackBox alive(n + 5);

    a.clear();
    int idx = 0;
    for (auto &[key, val] : freq) {
        a.push_back(key);
        alive.set(idx, val);
        idx++;
    }

    int ans = 0;

    // Apply the operation right now.
    int unsafe = lower_bound(a.begin(), a.end(), x * k) - a.begin();
    ans = unsafe;

    unsafe = lower_bound(a.begin(), a.end(), x) - a.begin();
    for (int i = unsafe; i < n; i++) {
        alive.set(i, min(alive.get(i), 1));
    }

    int taken = 0;
    for (int now = unsafe - 1; now >= 0; now--) {
        taken++;
        alive.add(now, -1);

        // Now, do the operation.
        // Overflows will never happen. Think why.
        unsafe = lower_bound(a.begin(), a.end(), a[now] * k) - a.begin();

        int remain = alive.range_sum(now, unsafe - 1);
        ans = max(ans, taken + now + remain);
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        int n;
        long long x, k;
        cin >> n >> x >> k;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a, x, k);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

class BlackBox {
  public:
    int n;
    vector<int> suff;
    BlackBox(int n) {
        this->n = n;
        suff.resize(n);
    }

    void set(int idx, int val) {
        suff[idx] = val;
        if (idx < n - 1) {
            suff[idx] += suff[idx + 1];
        }
    }

    int range_sum(int l, int r) {
        if (l > r) {
            return 0;
        }
        int sum = suff[l] - (r < n - 1 ? suff[r + 1] : 0);
        return sum;
    }
};

void solve(vector<long long> &a, long long x, long long k) {
    int n = a.size();

    map<long long, int> freq;
    for (int i = 0; i < n; i++) {
        freq[a[i]]++;
        freq[a[i]] = min(freq[a[i]], 2);
    }

    n = freq.size();
    BlackBox rsq(n);
    vector<int> alive(n);

    a.clear();
    int idx = 0;
    for (auto &[key, val] : freq) {
        a.push_back(key);
        alive[idx] = val;
        idx++;
    }

    int ans = 0;

    // Apply the operation right now.
    int unsafe = lower_bound(a.begin(), a.end(), x * k) - a.begin();
    ans = unsafe;

    unsafe = lower_bound(a.begin(), a.end(), x) - a.begin();
    for (int i = n - 1; i >= unsafe; i--) {
        alive[i] = min(alive[i], 1);
        rsq.set(i, alive[i]);
    }

    int taken = 0;
    for (int now = unsafe - 1; now >= 0; now--) {
        taken++;
        alive[now]--;
        rsq.set(now, alive[now]);

        // Now, do the operation.
        // Overflows will never happen. Think why.
        unsafe = lower_bound(a.begin(), a.end(), a[now] * k) - a.begin();

        int remain = rsq.range_sum(now, unsafe - 1);
        ans = max(ans, taken + now + remain);
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        int n;
        long long x, k;
        cin >> n >> x >> k;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a, x, k);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

class BlackBox {
  public:
    int n;
    vector<int> pref;
    BlackBox(vector<int> &a) {
        this->n = a.size();
        pref = a;
        for (int i = 1; i < n; i++) {
            pref[i] += pref[i - 1];
        }
    }

    int range_sum(int l, int r) {
        if (l > r) {
            return 0;
        }
        int sum = pref[r] - (l ? pref[l - 1] : 0);
        return sum;
    }
};

void solve(vector<long long> &a, long long x, long long k) {
    int n = a.size();

    map<long long, int> freq;
    for (int i = 0; i < n; i++) {
        freq[a[i]]++;
        freq[a[i]] = min(freq[a[i]], 2);
    }

    n = freq.size();
    vector<int> alive(n);

    a.clear();
    int idx = 0;
    for (auto &[key, val] : freq) {
        a.push_back(key);
        alive[idx] = val;
        idx++;
    }

    int ans = 0;

    // Apply the operation right now.
    int unsafe = lower_bound(a.begin(), a.end(), x * k) - a.begin();
    ans = unsafe;

    unsafe = lower_bound(a.begin(), a.end(), x) - a.begin();

    for (int i = n - 1; i >= unsafe; i--) {
        alive[i] = min(alive[i], 1);
    }

    int taken = 0;
    BlackBox rsq(alive);
    int orig_unsafe = unsafe;
    for (int now = unsafe - 1; now >= 0; now--) {
        // Now, do the operation.
        // Overflows will never happen. Think why.
        unsafe = lower_bound(a.begin(), a.end(), a[now] * k) - a.begin();

        int right = rsq.range_sum(now, unsafe - 1);
        right += max(0, orig_unsafe - unsafe);
        ans = max(ans, now + right);
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        int n;
        long long x, k;
        cin >> n >> x >> k;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a, x, k);
    }
    return 0;
}