CT60426

Theo's Ledger of weights

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the canyon post of Redrock with crates of weights, and Theo the assayer must account for every last one. Task: Print the number of inversions: index pairs (i,j) with i<j but a[i] > a[j]. Input format: First line: n. Second line: n integers. Output format: Print the inversion count (fits 64-bit). Constraints: 1 <= n <= 1439; 0 <= a[i],x <= 1000000.

Example 1:

Input: 188 186 148 99 1 169 72 76 152 37 98 66 137 87 18 172 85 170 17 175 10 8 187 131 77 90 149 180 46 88 138 158 156 91 9 80 53 126 100 68 119 47 22 165 74 160 73 41 39 52 135 123 56 57 166 109 30 162 69 94 151 112 154 3 136 141 81 4 103 48 79 62 107 159 104 128 84 60 105 29 122 134 19 12 95 163 182 13 7 155 171 111 176 113 58 183 33 86 124 97 150 49 92 142 27 185 75 181 115 161 51 125 108 5 38 147 45 61 132 59 21 16 130 118 65 184 121 44 11 78 96 139 106 15 116 83 23 67 117 153 173 43 20 120 145 36 0 110 127 14 24 55 157 101 50 129 25 177 2 146 114 35 63 140 34 64 28 178 42 31 179 71 40 6 93 102 82 167 164 174 70 168 144 54 32 133 143 26 89
Output: 9162

Example 2:

Input: 668 99159 557679 602668 447375 810368 119472 449905 124511 893496 838891 566877 346818 529016 590173 723957 438141 207997 296132 329220 60261 59940 838400 693138 746492 805547 738845 548109 780877 76970 370697 802510 880725 482092 395786 278889 675746 575232 753172 457997 116862 842747 9903 675106 983565 816970 278636 243023 985403 458645 566145 984954 455752 278282 669799 970050 454607 877046 672419 157728 851625 756965 764718 13737 144405 512666 163337 936851 136230 367838 271533 331977 385846 354869 581501 378384 27909 255886 434043 209788 124407 392673 110619 625087 561465 563642 184049 423569 972268 609489 933887 143330 103453 76401 506462 342857 688869 812813 811174 707419 773189 916305 938629 36265 78514 970957 362184 190482 93557 367238 546347 886067 753814 430289 808614 986489 228…
Output: 113356

Example 3:

Input: 173 70 0 75 128 154 1 139 160 152 149 157 163 159 158 48 135 132 58 59 34 53 62 56 164 119 76 19 109 35 106 155 92 14 97 124 45 90 111 22 43 96 84 6 108 54 123 102 105 30 77 137 31 165 13 134 71 67 141 117 116 151 47 85 73 64 33 49 40 125 8 2 133 153 172 17 61 114 72 42 4 82 93 39 11 80 100 131 37 3 143 50 7 32 10 167 121 29 57 12 169 44 68 138 156 60 89 78 112 120 91 144 98 66 27 15 69 95 146 147 140 79 122 23 20 145 52 150 38 170 148 28 118 18 162 41 171 126 24 161 166 99 16 55 81 115 107 110 46 113 25 130 83 127 65 87 101 129 142 36 104 86 21 26 103 5 74 9 88 51 136 94 168 63
Output: 7620

Constraints:

1 <= n <= 1439; 0 <= a[i],x <= 1000000.

Loading...
Test Cases:No test cases
No test cases available.
Theo's Ledger of weights - MEDIUM Coding Problem | CodeTikki