CT55500

The Disorder Count Beneath Stillwater

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the crane marshes of Stillwater; Gino weighs the day's crates manifests and starts the calculations. 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 <= 3836; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 1176 838530329 459420840 278202797 179058298 66981651 221361730 214039363 282792106 126874025 126863116 638012730 956774744 507325171 708712448 458274368 606228143 736821113 160007146 498103474 630364717 832116172 68275887 975966559 532606003 767720386 816738267 402356337 309372260 680412746 244368300 342043208 161495438 29282138 173023386 147994351 596703735 417334958 42857197 161515914 403424630 166630473 221702767 152520480 604080916 614102557 868263519 745561364 48075170 517256056 737716101 689489813 776135080 892810857 616527212 674392142 288452541 488730608 150502156 860326380 106618577 701749865 366120318 173953714 197652250 229516408 641408192 131485005 128444074 601446649 957931581 607659200 721553961 40920810 543704233 824625664 600409448 634204639 346759707 82102862 717888190 77…
Output: 343830

Example 2:

Input: 1142 892 458 189 197 665 654 462 293 696 715 409 324 434 963 116 23 1121 466 85 778 386 847 883 252 576 890 1091 469 0 1006 939 362 792 196 485 775 231 349 746 452 37 340 285 698 337 621 86 385 755 992 1096 973 177 278 592 907 1129 507 558 608 241 1023 782 82 35 257 78 108 801 774 734 809 999 946 947 626 1011 904 423 345 115 660 274 978 447 936 693 756 284 799 553 854 804 465 283 242 394 543 831 711 793 1100 510 903 560 328 1081 353 418 617 175 733 358 833 667 71 305 661 819 1004 581 896 356 850 971 1025 31 769 38 89 131 506 173 216 760 158 247 914 846 1101 182 184 272 1135 162 840 351 379 212 255 56 408 1056 614 524 921 171 411 13 893 17 912 1075 666 344 453 796 120 895 280 1064 52 494 625 53 534 122 1126 682 145 613 678 699 920 677 166 254 545 486 974 1085 164 183 924 342 875 1074 1010 1…
Output: 325366

Example 3:

Input: 3063 842014073 720394791 500352580 265257514 841767786 880607582 698552769 907430101 68501665 34680793 81136673 791619823 357602976 542704780 179796043 395972122 473319 772431552 63288682 429674288 737794124 203988654 421832715 990157431 324770170 731663050 559361055 807813073 693354944 45685706 727910655 12405161 240251702 569720112 718402304 969302079 973711346 949087255 457110627 611705977 376068443 615756772 114811485 152296766 720335260 980962287 835867215 208223826 45259175 118110360 450892254 557876329 517084586 7159451 534128188 472256045 251635186 544120872 626120308 67407616 410726775 625165523 869385073 446175816 44249281 438303212 486133321 991234292 450319562 385321151 558402928 930728243 273500698 335375497 331379215 956772900 125886454 117674267 58983657 730053156 111846561 …
Output: 2371964

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Disorder Count Beneath Stillwater - MEDIUM Coding Problem | CodeTikki