Editorial for Easy Peasy, Lemon Squeezy 2

Prerequisites: Binary Indexed Tree/ Policy Based Data Structure/ Merge sort

Explanation: This is a code for insertion sort. You have to count the number of swaps required to sort the array AA in non-decreasing order. This can be easily done using Binary Indexed Tree/ Policy Based Data Structure/Merge sort.

Binary Indexed Tree/Policy Based Data Structure: Count number of pairs (i,j)(i,j) such that Ai>AjA_i >A_j where, 1i<jN1\leq i< j\leq N

Merge Sort: Count number of swaps required during sorting the two halves and merging them.

Time Complexity: O(NlogN)O(NlogN)

Solution:

Setter’s solution (using BIT): https://ideone.com/KG82oX

Alter’s solution (using PBDS): https://ideone.com/Wav3uC

    Statistics


    45% Solution Ratio

    TanjumEarliest, 3M ago

    YouKnowWhoFastest, 0.0s

    YouKnowWhoLightest, 524 kB

    u1904103Shortest, 574B

    Toph uses cookies. By continuing you agree to our Cookie Policy.