CT57738

The Beryl Disorder Count

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the dune sea of Caravanrest, Parth records each registers in a worn leather ledger. The guild wants answers, not guesses. 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 <= 3706; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 2082 1493 677 781 307 616 413 1059 104 911 1128 1071 383 1045 1803 1025 521 1039 1218 33 1902 584 531 1340 691 937 1489 592 256 541 1323 1387 1435 1372 667 947 1331 214 1006 802 436 1605 1463 1221 901 701 266 1151 1818 2045 1958 179 2052 2024 1477 1179 679 289 1692 595 874 1283 274 1614 2042 379 1698 2066 1303 1095 1525 384 1160 664 270 456 657 1089 1927 275 787 1306 1706 380 2040 414 381 1689 342 1699 1632 2034 1841 449 22 58 115 1370 2051 1228 1859 1455 1106 2058 1141 1428 831 181 277 1598 678 622 359 279 486 1966 460 1626 1687 134 126 1163 2004 562 1461 998 1537 981 1743 961 1062 693 1553 1255 1931 795 1941 1591 1412 1760 1359 1620 497 1282 36 317 1674 1200 90 35 1036 263 1555 110 1570 200 1211 444 150 1568 1444 651 988 130 340 1191 176 168 1182 1978 322 656 1530 563 1654 185 1314 882 1…
Output: 1079971

Example 2:

Input: 2654 -244515 419781 855798 -315103 903690 -177132 -672786 612784 499243 -995048 35779 81902 -219275 -766938 -73174 -982976 -730078 375128 660581 548822 502041 -61389 -285004 -706950 890896 -286043 -196382 -728265 -791230 -372784 -870891 366205 329317 -663618 365040 564386 166988 43535 -201519 -502446 -218882 818166 -436318 -696001 163350 515015 -790057 -288189 537026 -360733 -141265 437779 861633 527040 -699250 52209 -46184 -488589 -807483 -518213 248389 114266 -281996 -925675 -933995 -346023 -96861 298350 -682597 164221 -154384 -310700 -456397 129166 667098 943576 328332 -822983 -964758 569686 149148 149372 -721740 698987 427744 399709 814252 -501642 931172 441592 992699 -664021 120509 -939437 850316 -418028 40424 100713 462537 524448 14937 -620015 -798503 657827 -453727 229415 -705459 68…
Output: 1765229

Example 3:

Input: 199 -833348 -329085 174446 -717228 29218 79779 -14124 -329114 763887 620312 6191 -45507 709188 44974 269411 440768 686327 586143 -135150 -13426 863075 -960526 767163 659246 -144719 579319 -455245 -101043 -658882 -102869 681234 433405 931887 193715 -746388 -596859 -234242 -739368 76342 -810451 -705428 740946 -173456 -45436 359 -750431 685303 518990 -442694 645 -629741 -654066 574483 -93730 470332 615338 93170 276446 -344696 102430 802842 413903 258038 -900439 -70613 -380631 -34057 -990021 441952 442724 31065 432692 -949921 -719357 607028 -341040 -147471 306806 339714 667529 -919689 461656 -879311 -414422 324716 -736026 564889 -333970 -136751 889743 920296 747861 947348 996342 -829428 900168 -681895 434512 228002 527301 -91724 -98336 651653 747798 98212 -748989 -338741 225271 -216450 -962369…
Output: 10173

Constraints:

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

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