CT50540

Orin's Disorder Count Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the maple sugarbush of Saprun. Orin spreads the ledgers records across the table and picks up a sharp pencil. 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 <= 3026; 0 <= a[i],x <= 1000000.

Example 1:

Input: 465 103 230 125 9 332 329 212 218 338 110 321 403 300 177 71 205 231 274 173 53 123 107 82 278 232 1 263 207 243 224 462 286 91 104 249 63 251 62 257 448 384 265 11 443 222 160 360 168 151 395 323 117 390 464 442 156 451 424 40 375 436 357 74 119 258 334 88 267 226 412 8 152 305 382 396 434 328 15 99 148 297 456 159 36 445 262 250 92 453 433 233 271 143 106 426 208 196 90 80 101 247 6 285 158 372 135 81 342 161 355 325 260 193 13 49 163 303 72 111 155 200 364 47 46 441 288 175 246 421 351 369 33 358 129 141 239 352 368 362 203 429 132 340 228 422 461 73 95 137 432 42 124 76 370 3 58 359 142 184 120 122 446 115 98 105 346 54 408 86 121 306 361 167 374 209 41 337 277 371 405 302 202 109 112 291 248 188 21 23 28 14 43 45 298 0 172 4 64 413 333 430 283 89 20 77 317 330 367 192 214 149 324 65 2…
Output: 52237

Example 2:

Input: 2181 596247 213761 560841 790876 297202 577853 465951 552013 181258 685819 531277 865910 981682 315200 281717 60459 921688 39605 822792 1282 466471 158625 172741 321189 579348 133479 911884 700500 971277 135718 557153 362924 469469 893723 407742 299846 761926 316390 50277 13459 622797 8220 516131 885428 391183 132158 614857 917037 183362 17904 573384 648777 347000 88726 387127 350946 108181 171193 828802 753369 698970 530019 748161 822042 884607 545953 241588 631689 42268 675902 833049 417353 195740 924456 447225 786844 468149 127058 224596 617601 978420 104054 750980 33609 11982 572458 262749 45518 487651 458078 788934 481079 147346 603830 25998 586486 294427 810933 680451 663871 752910 118335 293465 12261 80596 66999 87520 210082 882619 638109 306227 265994 297467 66718 5725 247875 52685…
Output: 1161882

Example 3:

Input: 1291 823480 677542 508194 501661 54418 603805 207065 62020 402893 228179 635469 750698 730562 761299 873617 385251 185183 512305 934113 296351 210625 134929 22754 710916 731143 587845 382651 170057 5409 211341 549186 518047 717761 658636 231554 472301 353617 596685 169276 816122 972330 252594 355 483690 380771 297324 737499 899925 363390 863827 970130 388501 290920 371194 137271 236930 397372 697924 251224 356531 561829 859823 471621 913099 549045 345446 75483 331349 335717 42439 304639 96041 223187 389330 398661 145683 145077 935762 178119 66600 344761 789173 431818 745646 321986 315537 501833 396158 332392 798140 32579 972117 34039 37038 588008 615303 152325 572730 660347 187949 354863 996598 440646 352751 745342 581234 220957 561653 665889 585923 196698 90079 74328 64992 46452 160242 13…
Output: 400669

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Orin's Disorder Count Ledger - MEDIUM Coding Problem | CodeTikki