CT54147

The Caravanrest Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Zane inherited the loom house at the dune sea of Caravanrest along with its curious bookkeeping system for weights. Time to make sense of it. 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 <= 1245; 0 <= a[i],x <= 1000000.

Example 1:

Input: 1022 366601 7588 524013 497146 254609 258239 221294 488233 419840 613578 392306 757550 794725 758059 315558 558894 433672 633040 781536 16232 111657 795964 744170 959986 427184 389684 288578 385281 986544 940550 281594 941956 936878 303922 961829 417198 189515 933214 383334 111497 742622 207026 266476 327722 114150 926176 323322 831767 991409 983503 994892 74856 847288 231630 859344 353766 416881 28313 375532 103013 192242 494459 686300 309951 891224 614192 427044 172407 243592 810698 354211 385332 679766 651781 521036 986253 293344 53716 302060 997799 657814 543935 426806 190158 868474 202400 777117 359203 760655 712707 398238 155906 8003 317973 867679 953957 850987 647586 265291 997566 261219 307362 518302 28644 50732 443164 337902 904451 893130 32029 564113 764412 85197 831572 149868 69…
Output: 256471

Example 2:

Input: 1171 167679 443126 800826 392352 447308 892415 356067 73421 865934 500054 733429 159234 902673 586263 601126 448469 957875 557052 861133 293143 680598 98448 200067 24418 533731 585045 96532 43348 719012 462318 974153 518029 271200 363639 283377 140915 291750 896380 458175 962083 355760 141689 215038 763205 966458 567311 113764 697521 293191 270714 304201 720569 453104 122323 410598 838631 830522 495041 500502 728992 779768 954169 967458 764183 25422 371489 481596 207813 387898 312760 534460 626032 443118 670339 433856 974943 959223 801176 929813 507322 136929 327561 35401 458680 725919 901863 122646 304323 772947 23971 906427 151965 775930 121794 849672 671245 75206 173898 843488 903098 343994 364083 711281 52346 464308 666224 910640 104915 521813 639492 234958 988798 455051 909315 757451 …
Output: 343514

Example 3:

Input: 1121 669 10 956 949 735 169 667 588 260 565 250 988 104 516 385 1084 29 6 1080 936 249 440 1107 322 910 1097 582 483 760 978 595 519 853 843 84 274 794 764 247 241 958 224 1033 1093 375 763 661 351 730 423 136 619 226 554 603 277 561 334 762 371 478 272 874 742 124 469 1044 706 902 380 435 146 1085 745 532 190 797 1012 165 437 399 629 259 1061 118 459 690 1109 992 831 892 1090 232 574 847 951 841 943 905 1008 866 800 825 217 369 830 484 303 743 122 28 938 549 333 807 528 90 150 1011 840 1064 752 422 159 474 100 288 1022 969 414 61 32 585 95 126 170 984 1019 765 310 834 430 72 98 373 173 177 257 696 69 555 793 872 99 154 676 975 97 131 773 987 962 948 63 472 168 594 1065 749 665 114 845 790 1114 503 482 820 12 68 449 672 602 693 816 81 912 1087 705 965 923 75 741 346 238 188 1023 787 925 89…
Output: 318243

Constraints:

1 <= n <= 1245; 0 <= a[i],x <= 1000000.

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