The code I am using is:

vector<int> countSmaller(vector<int>& nums) {

vector<int> result = nums;

multiset<int> data;

for (int i = nums.size() - 1; i >= 0; i--) {

auto it = data.lower_bound(nums[i]);

int dis = distance(data.begin(), it);

result[i] = dis;

data.insert(nums[i]); //It should be log(n), right?

}

return result;

}

It timed out.

I updated a little bit by changing the multiset into vector and it worked:

vector<int> countSmaller(vector<int>& nums) {

vector<int> result = nums;

vector<int> data;

for (int i = nums.size() - 1; i >= 0; i--) {

auto it = lower_bound(data.begin(), data.end(), nums[i]);

int dis = distance(data.begin(), it);

result[i] = dis;

data.insert(it, nums[i]);

}

return result;

}

I feel the time complexity for both is supposed to be O(nlogn), but why using set is slower?