CT41777

The Disorder Count at Beeswick

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the honeycomb cliffs of Beeswick as Scribe unrolls the day's manifest of shelves. The tally will decide the next shipment. 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 <= 1783; 0 <= a[i],x <= 1000000.

Example 1:

Input: 959 652682 151667 424465 311397 648205 865377 643669 377206 859334 451955 231944 994550 492352 931577 483177 576529 768284 404859 662701 328018 661344 899660 433588 573410 11516 29302 546594 80469 333882 918303 38840 642543 824649 255195 571274 504792 680667 294893 771844 4786 979824 68164 786652 372478 468725 975066 374600 478048 750614 243840 827708 808409 119552 276512 686925 698562 841745 72428 24963 566455 961156 821856 502149 467815 978657 612219 388118 938374 242141 248786 897771 171766 570882 297864 557689 27668 298816 790963 175205 857586 184021 610894 575948 502397 776382 264674 249787 691068 47199 390779 21457 561761 969331 72132 545240 636449 882984 420983 808355 427276 949866 372323 907279 761635 111556 208589 476281 938829 802163 996357 22023 566347 92369 613602 635435 371022…
Output: 225630

Example 2:

Input: 605 290932 380557 923702 815870 345674 559642 15739 184242 411623 440513 229382 85031 231726 798241 143607 870838 33795 939762 7671 960290 64558 391071 313682 736223 359800 421222 679024 592763 617027 241488 844657 992294 409077 888107 626300 450616 247629 16396 257273 859006 574847 19891 989793 882392 62995 550205 870239 205433 112603 194446 202978 769128 411289 75691 845245 608538 638904 982580 740749 488793 501741 461319 228386 9562 489674 77889 351315 435752 486772 751946 860876 105611 760916 561425 804220 167701 53988 32583 172425 390625 616348 749381 33113 412109 534571 452810 52966 939412 302012 157165 684958 823127 743593 528200 728808 278818 134558 485129 653914 209975 395372 434085 662041 485006 450412 240722 852097 211472 344244 830531 600102 914138 257636 84015 350543 693865 91…
Output: 94060

Example 3:

Input: 320 279276 4402 274324 316041 362177 647792 773680 980340 693266 541759 287016 421329 134865 870359 539590 979553 831147 524592 129240 193470 426696 716461 500527 354476 538683 245826 243913 293321 272067 550579 305963 365559 531407 653511 618859 49097 613812 223467 271065 795116 882643 948462 47045 34573 59735 108210 141977 882728 806711 521705 565753 102252 943505 812769 686013 568123 179383 698547 616344 724827 79923 70945 369343 533146 561822 619777 779962 45285 931310 79806 852647 184064 321398 686976 619927 451848 879056 337865 52200 773673 120934 888236 640034 828292 37148 154757 11386 335194 29226 237190 755758 812623 217494 859187 971732 110121 975579 908061 423352 786462 598157 156441 839386 539842 684408 383387 100670 129228 546297 468241 639575 616149 36009 954517 304535 758928…
Output: 24542

Constraints:

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

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