CT60010

The weights Disorder Count Puzzle

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the lantern reef of Glowtide, someone must balance the workshop's books. This year the task falls to Elowen, armed only with the weights register. 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 <= 3338; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 668 665175382 321153658 25363682 967001694 926381258 359552008 85046371 855319579 800853201 177592106 598575829 544591148 895551053 838957398 970764676 778988226 87042066 843335542 19242183 794092406 400070735 562705932 733546815 443375017 61463722 681859599 357831695 293244816 158778123 845969720 832412602 170967670 678619942 349099505 803201009 562947744 117805319 359709167 424015759 117331209 38210442 685621379 200785152 123999085 443394457 724511827 956937760 4674505 565506681 891339763 702549360 909022690 148882933 865907680 68176758 105374198 670201347 791333714 683709265 336216411 718430922 152691704 205335553 297611377 497957254 262446691 745257468 232769222 775340587 248163859 762653879 639649908 760765467 700111201 887435057 474032446 846016253 980055807 258996422 969486957 55142…
Output: 117162

Example 2:

Input: 2225 106634152 828987273 324583283 691556492 725446107 219499535 663014776 710395392 718365541 477834033 374207447 12214162 792337906 955488496 752763481 902595403 20754693 548328199 810699108 749703176 734596643 700973170 465593869 174178254 938390338 613491786 702746671 926463300 22867576 784498916 456164886 470140730 356730521 520040101 479753714 665501940 183901253 297961701 382597584 488122777 170878170 235996183 137011641 111304651 361696949 439202528 516759127 316765811 4987730 703333240 829816267 237546335 731835893 19456713 418157504 187041598 89898960 291693998 167375936 661097805 696598570 627687620 190809580 921818401 793225578 716748907 137194013 57772687 633046152 633523130 947636411 425669711 671496813 332218534 161566892 745848610 86159045 457617424 300486183 997719064 1577…
Output: 1262760

Example 3:

Input: 150 320680289 119693419 544985120 323239375 727892430 372113452 91888995 506934426 54243370 912732746 793479678 903687828 658594599 722190448 354847835 393487535 829709502 910067795 742655050 476513432 558825433 605660948 22818072 428987127 912697567 653469771 576373267 197648528 340215725 801121104 4524242 260930559 652290240 648496320 658560015 174319079 915124702 313677818 461660545 910043028 459831468 147778729 118778760 567860186 475551604 538382661 976823950 766418240 475832669 546355606 997810568 851364947 662059988 479949858 196250880 343525673 25616560 702763773 799879333 373250518 639176341 346543576 484017447 906506314 717124634 523261959 365846011 989411442 216004832 341727159 513132 820634741 109460614 841729684 923885606 675153857 56061250 144719794 771398913 355009149 957074…
Output: 5809

Constraints:

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

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