CT48474

Last shelves of Faye

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Faye the archivist watches over the kelp forests of Tangledeep's stores of shelves. A careful computation stands between order and chaos. 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 <= 3768; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 57 817790872 538324542 908214707 246953141 21693721 132095444 777407325 479695485 87026252 673466423 588910314 637846352 537937080 757418468 562613656 543401432 346967335 362339925 314933822 50738123 694713968 381244600 881730514 849355218 182777946 290647905 163940856 725493077 130895696 997227887 152670954 563506447 721821450 9125302 384233541 693258913 280986794 251101352 735039055 459208708 555353603 870630205 560826116 475470510 627623454 982400778 133474362 774462485 855159042 139458751 320127288 531321177 698444111 268186717 839766229 419243112 971509186
Output: 747

Example 2:

Input: 974 997542999 322015941 161526947 820714554 455819612 448485760 150915508 314148621 486796100 466093321 883984002 69089883 914629604 951377123 82312483 668195269 767907520 678662616 603188338 430384994 519740690 216035395 154066406 626225018 403967080 292067637 234023579 355952458 163012809 985923484 803218544 276456991 92485493 324176505 742672535 880409862 529048482 287665249 393671123 311322979 480115348 311801458 550475823 470869986 626931310 250194154 694800543 942529517 262789057 111851901 905008573 830154236 860223998 476101476 276337284 209391448 746505589 84941705 584598065 30257948 861336898 143036629 930329724 987378423 471311100 425922863 76177322 281065313 865994702 325907261 416957912 586614563 809484679 957538944 215985685 80783448 581088552 6886725 809534946 625573500 16045…
Output: 246310

Example 3:

Input: 97 71 59 23 67 92 77 12 52 42 22 10 96 89 25 78 0 91 5 21 51 19 16 82 58 54 84 70 85 28 80 11 65 31 40 18 35 94 73 17 7 14 43 27 8 1 36 64 44 86 72 32 83 46 45 3 76 49 48 50 47 55 4 41 66 38 90 37 81 69 15 39 57 13 33 95 61 74 53 30 34 93 6 20 56 26 2 75 29 62 68 88 9 87 60 63 24 79
Output: 2304

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.