Sorting books

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define INF 1e9

struct MergeSortTree
{
    int n;
    vector<vector<ll>> seg;

    MergeSortTree(const vector<ll> &a)
    {
        n = (int)a.size();
        seg.resize(4 * n);
        build(0, 0, n - 1, a);
    }

    void build(int node, int l, int r, const vector<ll> &a)
    {
        if (l == r)
        {
            seg[node] = {a[l]};
            return;
        }
        int mid = (l + r) / 2;
        int left = 2 * node + 1;
        int right = 2 * node + 2;
        build(left, l, mid, a);
        build(right, mid + 1, r, a);

        seg[node].resize(seg[left].size() + seg[right].size());
        std::merge(seg[left].begin(), seg[left].end(),
                   seg[right].begin(), seg[right].end(),
                   seg[node].begin());
    }

    int countLessThan(int ql, int qr, ll x)
    {
        return countLessThan(0, 0, n - 1, ql, qr, x);
    }

    int countLessThan(int node, int l, int r, int ql, int qr, ll x)
    {
        if (qr < l || r < ql)
            return 0;
        if (ql <= l && r <= qr)
        {
            return std::lower_bound(seg[node].begin(), seg[node].end(), x) - seg[node].begin();
        }
        int mid = (l + r) / 2;
        int left = 2 * node + 1;
        int right = 2 * node + 2;
        return countLessThan(left, l, mid, ql, qr, x) +
               countLessThan(right, mid + 1, r, ql, qr, x);
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<ll> A(n);
    for (int i = 0; i < n; ++i)
    {
        std::cin >> A[i];
    }

    MergeSortTree mst(A);
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        res += mst.countLessThan(A[i - 1], A[i + 1], A[i]);
        // cout << mst.countLessThan(l, r, x) << "\n";
    }
    cout << res * 2 << '\n';
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: ACCEPTED

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: ACCEPTED

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: WRONG ANSWER

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: ACCEPTED

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: WRONG ANSWER

Test 24

Verdict: ACCEPTED

Test 25

Verdict: WRONG ANSWER

Test 26

Verdict: WRONG ANSWER

Test 27

Verdict: WRONG ANSWER

Test 28

Verdict: ACCEPTED

Test 29

Verdict: WRONG ANSWER

Test 30

Verdict: WRONG ANSWER

Test 31

Verdict: WRONG ANSWER

Test 32

Verdict: WRONG ANSWER

Test 33

Verdict: WRONG ANSWER

Test 34

Verdict: WRONG ANSWER

Test 35

Verdict: WRONG ANSWER

Test 36

Verdict: WRONG ANSWER

Test 37

Verdict: WRONG ANSWER

Test 38

Verdict: WRONG ANSWER

Test 39

Verdict: WRONG ANSWER

Test 40

Verdict: WRONG ANSWER

Test 41

Verdict: WRONG ANSWER

Test 42

Verdict: WRONG ANSWER

Test 43

Verdict: WRONG ANSWER

Test 44

Verdict: WRONG ANSWER

Test 45

Verdict: WRONG ANSWER

Test 46

Verdict: WRONG ANSWER

Test 47

Verdict: WRONG ANSWER

Test 48

Verdict: WRONG ANSWER

Test 49

Verdict: WRONG ANSWER

Test 50

Verdict: WRONG ANSWER

Test 51

Verdict: WRONG ANSWER

Test 52

Verdict: WRONG ANSWER

Test 53

Verdict: WRONG ANSWER

Test 54

Verdict: WRONG ANSWER

Test 55

Verdict: WRONG ANSWER

Test 56

Verdict: WRONG ANSWER

Test 57

Verdict: WRONG ANSWER

Test 58

Verdict: WRONG ANSWER

Test 59

Verdict: WRONG ANSWER

Test 60

Verdict: WRONG ANSWER

Test 61

Verdict: WRONG ANSWER

Test 62

Verdict: WRONG ANSWER

Test 63

Verdict: WRONG ANSWER

Test 64

Verdict: WRONG ANSWER

Test 65

Verdict: WRONG ANSWER

Test 66

Verdict: WRONG ANSWER

Test 67

Verdict: WRONG ANSWER

Test 68

Verdict: WRONG ANSWER

Test 69

Verdict: WRONG ANSWER

Test 70

Verdict: WRONG ANSWER

Test 71

Verdict: ACCEPTED