include

using namespace std;

string ltrim(const string &); string rtrim(const string &); vector split(const string &);

class FenwickTree { public: FenwickTree(long size) : tree(size + 1, 0) {}

void update(long index, long value) {
    while (index < tree.size()) {
        tree[index] += value;
        index += index & -index;
    }
}

long query(long index) {
    long sum = 0;
    while (index > 0) {
        sum += tree[index];
        index -= index & -index;
    }
    return sum;
}

private: vector tree; };

long insertionSort(vector arr) { long shifts = 0; long maxElement = *max_element(arr.begin(), arr.end()); FenwickTree fenwickTree(maxElement);

for (long i = arr.size() - 1; i >= 0; i--) {
    shifts += fenwickTree.query(arr[i] - 1);
    fenwickTree.update(arr[i], 1);
}

return shifts;

}

int main() { ofstream fout(getenv("OUTPUT_PATH"));

string t_temp;
getline(cin, t_temp);

long t = stol(ltrim(rtrim(t_temp)));

for (long t_itr = 0; t_itr < t; t_itr++) {
    string n_temp;
    getline(cin, n_temp);

    long n = stol(ltrim(rtrim(n_temp)));

    string arr_temp_temp;
    getline(cin, arr_temp_temp);

    vector<string> arr_temp = split(rtrim(arr_temp_temp));

    vector<long> arr(n);

    for (long i = 0; i < n; i++) {
        long arr_item = stol(arr_temp[i]);

        arr[i] = arr_item;
    }

    long result = insertionSort(arr);

    fout << result << "\n";
}

fout.close();

return 0;

}

string ltrim(const string &str) { string s(str);

s.erase(
    s.begin(),
    find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
);

return s;

}

string rtrim(const string &str) { string s(str);

s.erase(
    find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
    s.end()
);

return s;

}

vector split(const string &str) { vector tokens;

string::size_type start = 0;
string::size_type end = 0;

while ((end = str.find(" ", start)) != string::npos) {
    tokens.push_back(str.substr(start, end - start));

    start = end + 1;
}

tokens.push_back(str.substr(start));

return tokens;

}

The template is ****!

First off it suggests that the results will fit in an int.

Secondly my code was too slow due to the large input. Then I modified their io template even further with ios::sync_with_stdio(true) and cin.tie(0) et voila Accepted.

Solved this by using binary indexed tree

class FenwickTree { public: vector tree; long size;

FenwickTree(long n) {
    size = n + 2;
    tree.resize(size, 0);
}

void update(long index, long value) {
    while (index < size) {
        tree[index] += value;
        index += index & -index;
    }
}

long query(long index) {
    long result = 0;
    while (index > 0) {
        result += tree[index];
        index -= index & -index;
    }
    return result;
}

long queryRange(long left, long right) {
    return query(right) - query(left - 1);
}

};

long insertionSort(vector arr) { long n = arr.size(); vector sorted = arr;

// Coordinate compression
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());

unordered_map<long, long> compress;
for (long i = 0; i < sorted.size(); ++i) {
    compress[sorted[i]] = i + 1; // 1-based indexing
}

FenwickTree bit(sorted.size());
long shifts = 0;

for (long i = 0; i < n; ++i) {
    long idx = compress[arr[i]];
    // Count number of elements already in BIT that are greater than arr[i]
    shifts += bit.queryRange(idx + 1, sorted.size());
    bit.update(idx, 1);
}

return shifts;

}

Hey everyone, I came across this solution and I'm curious if it can be implemented on my website. The website in question is Potlaki Export Group, where we specialize in exporting premium-quality products like poultry, seafood, foods & beverages, cosmetics, chemicals, and agricultural produce. We're always looking for innovative ways to enhance our services and ensure customer satisfaction. Would this solution work well with our current setup? Any insights or advice would be greatly appreciated. Thanks in advance!

First of all - please change return type to long, some test cases are meant to return number bigger than 32 bits

Second of all - I gave up for last 3 cases remaining xDD Exceeded time limits on them.. I reckon I need to something more with the rotation..

Here is my C++ solution:

long insertionSort(vector arr) {`

long shifts = 0;
int st_tail_idx = 1;

while (st_tail_idx < arr.size()) {

    int elem = arr[st_tail_idx];
    int tmp_shift = 0;
    int breaker_elem = 0;

    int low = 0;
    int high = st_tail_idx;
    while (low <= high) {
        int mid = (low + high) / 2;
        int guess = arr[mid];
        if (guess < elem) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    breaker_elem = arr[low];

    tmp_shift = st_tail_idx - low;
    int shift_correction = 0;
    if (breaker_elem == elem) {
        while (low + shift_correction < arr.size() - 1 && arr[low + shift_correction] == breaker_elem) {
            shift_correction++;
        }
    }

    tmp_shift -= shift_correction;
    if (tmp_shift > 0) {

        int new_pos = st_tail_idx - tmp_shift;

        int elems_pack = 1;
        if (st_tail_idx < arr.size() - 1) {
            int last_elem = arr[st_tail_idx + 1];
            for (int i = st_tail_idx + 1; i < arr.size(); i++) {

                if (arr[i] < elem || arr[i] >= breaker_elem || arr[i] < last_elem) {
                    break;
                }
                last_elem = arr[i];

                elems_pack++;
            }
        }

        std::rotate(arr.begin() + new_pos, arr.begin() + st_tail_idx, arr.begin() + st_tail_idx + elems_pack);
        shifts += tmp_shift * elems_pack;

        st_tail_idx += elems_pack;
    }
    else {
        st_tail_idx++;
    }
}

return shifts;

} `