CT39871

Last registers of Rune

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the desert outpost of Sandspire opens only for a perfect tally of registers. Rune means to find out. 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 <= 1808; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 1475 738113347 443052714 811675431 858174234 92886981 209184937 574537491 566089929 900875160 162788593 125470914 549967760 346969971 296361189 768736341 337157933 531818559 899925847 701227620 975731916 982040333 766574404 116721029 838352676 257637593 1931931 112935390 810327977 247461133 320200946 65586873 508966205 528635425 419368040 991052094 706064909 48335543 484980063 999662583 489814656 34960860 776434015 407185079 754479950 799917878 607793393 520357066 550020977 936287804 804651210 547674023 477177349 665752431 132034758 441098777 665990578 873837694 807282871 431662137 238296649 401669280 32311127 74544862 736813036 371411713 308852183 3514229 198251160 170311459 2421947 719953532 304357228 224945979 81977623 55842563 285389839 552013496 909460699 859690622 624158208 484357131…
Output: 538798

Example 2:

Input: 35 571841097 196146099 890962533 507707201 965051268 695618375 28948709 744713018 847562884 732726332 464158040 996890983 128937914 193248677 827609538 705939006 316446625 915388262 62904235 684457721 121111184 867001020 160816834 885412084 344750825 272847546 704648279 524419770 214929911 873366708 734912248 437064230 44281934 387683237 916886385
Output: 315

Example 3:

Input: 476 290127909 775240944 461510474 375589844 176487008 677047663 677992216 483947311 661457788 649815990 515999272 357681445 920673482 795025911 760821300 649437769 892169034 132185792 182025642 142639238 148093846 333942162 437382678 144619511 469424791 590265704 727125579 494384214 152006133 618929639 800797293 698485553 929820813 132401828 329694361 239991460 161552772 212970061 736702246 429864371 401771304 351415654 146322940 281476630 250158504 659076012 781584860 419701328 248988163 52789434 471279250 968490839 633609135 870944826 187855096 390622106 323239685 737818415 899059220 194251291 400289095 888374543 864557629 435051188 697512822 195236510 415953530 496579098 572132188 844999922 181230005 167528003 3299158 122972505 942676394 750576720 137309367 955440721 550587993 269951190…
Output: 55865

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Last registers of Rune - MEDIUM Coding Problem | CodeTikki