CT51494

The Disorder Count Beneath Lodebarrow

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the silver mines of Lodebarrow close for winter, Hema must finish the shelves ledger - one figure at a time. 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 <= 2104; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 358 56668 592437 -855688 -600316 -693363 -491606 657912 -749997 101390 -899624 -554978 106613 -551311 668325 444192 246883 448185 416707 315830 86038 547061 -474676 848439 -334348 -711090 721355 -551494 -710606 260342 118798 -443394 802933 -336722 -853321 -240500 -651243 -914339 -817101 115046 -367324 -976744 -904380 -76680 417873 137533 333067 -617289 899698 -624928 933887 -121032 -81181 694470 315487 495288 282336 -86469 -671610 817954 991349 -973326 -715543 288608 412464 -813907 873641 874826 289638 -95298 237178 -586717 -335912 335469 -115298 279420 -464354 -737643 -347399 -499099 -894921 -993788 650658 726780 909306 133046 358492 566708 -444024 -205951 -141419 953370 -489993 -18775 263219 -325277 544754 -441529 -745600 -691842 -196542 -720448 -2766 35738 -208195 -202550 627637 -528774…
Output: 31547

Example 2:

Input: 1659 224 1358 1007 1330 1200 583 845 618 1357 13 701 755 440 1110 743 874 1310 1 1642 1267 1645 292 996 772 396 1384 888 454 641 820 1203 118 112 1043 998 84 122 1214 197 1298 238 578 430 600 1361 1417 62 1413 1589 1363 334 266 1216 1364 278 1269 1324 1126 927 215 108 1221 561 837 674 1024 1560 373 1506 925 1179 894 590 1307 1294 529 1098 160 673 497 375 1036 348 490 1380 833 29 1340 1197 1066 1579 431 1012 538 997 825 851 426 99 1502 1443 678 1146 836 1124 884 1327 787 680 1276 242 736 1595 1348 917 1401 1246 1616 25 557 319 308 753 399 886 92 605 1183 571 1057 652 1427 893 1646 111 125 213 1359 1374 608 1608 1426 81 853 1460 793 1478 234 1328 1117 599 1192 785 471 1181 166 1332 269 434 1522 499 1027 663 68 1472 838 332 535 661 311 709 185 1229 340 693 1041 498 1064 1353 814 1537 89 98 15…
Output: 683384

Example 3:

Input: 804 644393 -642093 -532471 916841 89149 -271908 -725951 -57521 -572808 -863116 -256592 350062 -920458 -365881 -414550 -291963 -698254 -373854 893522 -79852 -929694 828204 672228 187927 -571962 996312 -224968 738781 368852 87557 -240017 222475 -834296 -985387 -284974 -431868 376274 21283 -641330 951353 567848 66984 121870 -563314 8502 430351 324756 -468193 529217 870695 339979 471314 -333634 270371 633605 696105 -742850 188305 -101802 -746435 511943 -606702 -814905 398099 646113 775046 369748 274014 588498 935002 -624599 -759071 309797 -412464 601670 -869449 989801 -157104 498838 -893659 -852310 381994 680875 -241712 606111 176488 352294 798406 -150311 -614535 -471261 -502630 -890261 789293 322078 -583803 476459 71828 -343947 506928 196032 -419401 883972 -460750 -761540 143435 417609 -60833…
Output: 162325

Constraints:

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

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