CT61402

Gita's Disorder Count Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Gita the auditor watches over the valley of Misthollow's stores of ledgers. 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 <= 3529; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 2358 796579864 760843948 705262975 63201900 198564097 135038296 347928035 529046283 92326215 867123343 879999770 160307970 865221316 476973033 276724645 206620961 762263870 386062601 219111020 542433604 661981203 923899773 659755204 22191990 924886386 450391441 200137952 707747461 961641353 876332583 418703969 236154834 86898195 700399290 443606318 778928441 215452174 586866170 997946612 778861357 185243005 81401122 63688383 868037613 66390550 650730654 570136837 271375213 773774363 645718105 328452841 319123883 889591422 456140605 948407459 653680610 956059984 543090908 82050392 835842567 922081019 903994697 398051590 142819613 441688759 504353318 201867028 684170263 515727644 468084320 221101566 859237663 609833338 60115835 18627852 686475318 688746763 240440406 175176497 709659216 51905…
Output: 1426848

Example 2:

Input: 3311 704861674 10062048 435178349 374776506 158556821 523047482 941603337 789674912 369872167 976827337 338650059 254198693 350883260 872718198 722153516 66824569 333982852 59709885 165050918 62085217 30254045 949474266 662235299 843474902 640601405 472745443 146963236 552733285 366587887 1080498 288197694 384295126 202236554 242182062 49870761 991598935 507174125 5430863 225602609 403539616 919752361 151420536 60496587 625011879 240695497 803823261 190155253 936801575 696436074 857236024 734624254 336210437 745914934 215119618 152733604 725218632 565324213 612745777 821871201 193443307 965931646 708347961 95646166 566708058 206615369 212700725 800175585 878218920 414281218 476717021 165246796 541218257 643835119 71835363 560214445 742607193 75804646 873881442 262540751 12629458 543924260 …
Output: 2731955

Example 3:

Input: 132 36 119 35 65 112 18 2 98 46 93 115 34 78 14 47 61 91 74 54 59 38 107 19 31 52 121 102 48 63 118 123 67 15 103 10 30 90 127 113 69 37 87 9 129 111 4 106 55 92 100 89 22 62 99 68 96 73 82 27 85 125 126 26 40 43 95 108 64 66 32 6 53 124 50 130 88 104 29 70 75 7 83 94 25 120 60 20 56 97 3 41 81 86 105 16 0 12 1 33 72 11 23 21 110 77 128 45 28 84 101 76 71 49 80 24 57 58 114 8 5 109 39 79 51 44 42 13 131 117 116 122 17
Output: 4499

Constraints:

1 <= n <= 3529; 0 <= a[i],x <= 1000000000.

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