Submission details
Task:Sorting books
Sender:aalto26dw_003
Submission time:2026-09-23 17:49:51 +0300
Language:C++ (C++20)
Status:COMPILE ERROR

Compiler report

input/code.cpp: In member function 'std::vector<int> Solution::countSmaller(std::vector<int>&)':
input/code.cpp:57:21: error: no match for call to '(std::vector<int>) (std::vector<int>::iterator, std::vector<int>::iterator)'
   57 |         sortedUnique(nums.begin(), nums.end());
      |         ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
using namespace std;

class BinaryIndexedTree
{
public:
    int size;
    vector<int> tree;

    // Initialize BIT with given size
    BinaryIndexedTree(int n) : size(n), tree(n + 1, 0) {}

    // Add delta to position x and propagate to all affected nodes
    void update(int x, int delta) {
        while (x <= size) {
            tree[x] += delta;
            x += lowbit(x);  // Move to next node that includes this position
        }
    }

    // Query prefix sum from index 1 to x
    int query(int x) {
        int sum = 0;
        while (x > 0) {
            sum += tree[x];
            x -= lowbit(x);  // Move to parent node
        }
        return sum;
    }

    // Get the lowest set bit of x (isolate rightmost 1-bit)
    int lowbit(int x) {
        return x & -x;
    }
};

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        // Step 1: Coordinate compression - get unique values
        unordered_set<int> uniqueNums(nums.begin(), nums.end());
        vector<int> sortedUnique(uniqueNums.begin(), uniqueNums.end());
        sort(sortedUnique.begin(), sortedUnique.end());
      
        // Step 2: Map each unique value to its compressed index (1-indexed for BIT)
        unordered_map<int, int> valueToIndex;
        int uniqueCount = sortedUnique.size();
        for (int i = 0; i < uniqueCount; ++i) {
            valueToIndex[sortedUnique[i]] = i + 1;  // 1-indexed for BIT
        }
        sortedUnique(nums.begin(), nums.end());

        // Step 3: Initialize BIT with compressed range size
        BinaryIndexedTree* bit = new BinaryIndexedTree(uniqueCount);
      
        // Step 4: Process array from right to left
        vector<int> result(nums.size());
        for (int i = nums.size() - 1; i >= 0; --i) {
            // Get compressed index of current number
            int compressedIndex = valueToIndex[nums[i]];
          
            // Update BIT: mark this number as seen
            bit->update(compressedIndex, 1);
          
            // Query how many numbers are smaller (indices 1 to compressedIndex-1)
            result[i] = bit->query(compressedIndex - 1);
        }
      
        return result;
    }
};

int main()
{
    int n;
    cin >> n;
    vector<int> array(n);
    vector<int> frequencies(n);
    for (int i = n - 1; i >= 0; i--)
    {
        cin >> array[i];
    }
    Solution solution;
    frequencies = solution.countSmaller(array);
    reverse(frequencies.begin(), frequencies.end());
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        count += i - frequencies[i];
    }
    cout << count;
}