Editorial: The Curious Kid and the Number Game

We are asked to count how many numbers are special based on two conditions:

• At least a[i] numbers ≥ a[i] on the right

• At least a[i] numbers ≤ a[i] on the left

A brute-force O(N²) solution is too slow.

We solve it in O(N log N) using ordered set (PBDS):

• Traverse right to left to count how many values ≥ a[i] on the right.

• Traverse left to right to count how many values ≤ a[i] on the left.

• If either count ≥ a[i], it's special.

This can also be solved using a Fenwick Tree or Segment Tree with similar time complexity.

Time Complexity: O(N log N)
Space Complexity: O(N)

Code :

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

template <typename T> using ordered_set = tree<T, null_type, less_equal<T>,rb_tree_tag, tree_order_statistics_node_update>;

vector<int> countGreaterRight(vector<int>& arr) {
int n = arr.size();
vector<int> res(n);
ordered_set <int>os;
for (int i = n - 1; i >= 0; i--) {
    res[i] = os.size() - os.order_of_key(arr[i]); // strictly greater
    os.insert(arr[i]);
}
return res;
}

vector<int> countSmallerLeft(vector<int>& arr) {
int n = arr.size();
vector<int> res(n);
ordered_set <int>os;
for (int i = 0; i < n; i++) {
    res[i] = os.order_of_key(arr[i] + 1); // strictly smaller
    os.insert(arr[i]);
}
return res;
}

int main() {
int n;
cin >> n;
vector<int>v(n);
for(int i = 0; i < n; i++)
{
    cin >> v[i];
    assert(v[i] < n);
}

vector<int> greaterRight = countGreaterRight(v);
vector<int> smallerLeft = countSmallerLeft(v);

int specialCount = 0;
for (int i = 0; i < n; i++) {
    if (greaterRight[i] >= v[i] || smallerLeft[i] >= v[i])
    {
        specialCount++;
    }
}

cout << specialCount << endl;

return 0;
}