CT53724

Envoy's Ledger of crates

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the fen lights of Will-o-Wisp as Envoy unrolls the day's manifest of crates. The tally will decide the next shipment. 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 <= 3105; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 1199 244775990 91204971 829869798 778712361 443240037 971146719 692826475 83808873 752014032 861432901 900354520 623692650 397258485 943282743 602186551 582019808 560583591 287698822 390469579 306983029 568160841 508445237 377963806 699783523 127037942 561930748 412846977 547290774 162478194 704078601 896994508 913337848 382741202 825064350 49644733 362674817 483033069 336532518 332698107 36469424 960800499 541989822 808131796 649564765 288006004 846011348 905248353 100624356 860976147 659173166 652324575 456016162 194949047 193071840 293077552 661465775 402480683 674075001 144609843 652693224 319806727 718314996 204607461 323741331 661675610 907196779 783554345 434775148 260116024 203664700 14690863 527000994 861155001 224086495 613812098 443912130 465335243 567593860 349987565 263504273 …
Output: 356197

Example 2:

Input: 286 114 166 201 214 211 39 133 77 203 193 200 215 19 218 6 255 159 272 168 83 148 188 249 5 127 150 40 230 119 11 95 282 256 152 129 14 269 96 8 244 279 189 47 59 265 21 236 50 242 117 134 262 172 136 142 176 70 101 264 160 190 79 147 277 17 111 97 122 209 82 135 23 254 232 74 182 98 204 202 43 197 102 185 143 63 16 54 71 75 60 10 225 226 174 283 2 28 284 27 42 141 210 222 163 118 248 178 121 149 88 69 26 22 213 130 93 146 170 68 219 110 177 80 165 257 66 171 164 128 90 194 223 169 241 199 115 104 161 145 261 18 155 258 195 7 131 234 278 55 24 198 237 167 243 45 32 229 25 158 72 273 33 91 85 20 208 73 250 61 31 78 99 48 125 268 44 151 267 192 275 140 57 51 34 217 191 65 52 263 103 76 154 107 181 36 206 196 246 46 207 106 67 9 212 184 251 245 37 12 109 3 233 247 49 231 62 29 271 138 108 220…
Output: 20335

Example 3:

Input: 2416 445975139 71819728 821871121 576580447 224347205 351520853 19121837 651357458 18997481 922522519 877302357 786390285 114466370 489031496 69972967 858278043 779284142 260392759 542164631 183760858 6112219 849546181 414040071 46151804 267889700 161056521 147237945 699150320 178141044 845666122 163736317 260876290 589462015 677333975 922272163 325858342 269940554 330793526 658826822 509513493 214687140 609684036 931760052 990644681 941606578 -729904 467803005 241655700 312121675 840418161 366811246 602495624 690287631 184942792 309877837 438501234 285289063 337962210 312849941 164675251 646913925 505966873 148515507 773494027 802583090 934565910 823389589 401581785 25893267 707428926 952799978 221898211 595269730 318491957 197149250 280877474 815472738 374214950 120665288 588243780 79613…
Output: 1439886

Constraints:

1 <= n <= 3105; -1000000 <= a[i],x <= 1000000000.

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