CT53356

The Bronze crates of Uma

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the bamboo terraces of Verdantstep. Uma spreads the crates records across the table and picks up a sharp pencil. 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 <= 3760; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 1430 652 136 59 867 845 529 576 1050 710 624 1165 419 907 787 298 355 1393 1321 763 17 881 740 420 400 769 541 1367 1133 276 502 791 414 558 1031 786 1040 60 1319 582 271 622 278 159 385 135 26 876 328 1155 1215 333 611 129 126 924 516 1092 83 1316 586 1366 505 672 1177 883 1000 13 351 606 1397 1369 224 207 648 612 656 1355 796 592 262 707 461 507 497 1347 1360 948 1043 1365 1042 285 1396 475 688 609 335 928 1121 216 711 236 177 903 646 23 1328 1262 942 933 965 640 314 336 978 966 1395 995 832 868 573 1287 935 1326 1079 1166 1066 607 1183 4 937 421 293 397 122 530 916 635 510 1290 1139 307 294 771 588 423 756 1335 1268 613 10 1230 977 1075 726 272 1105 65 911 1309 5 97 778 642 255 221 381 723 1032 43 681 1008 286 41 180 94 316 1162 1392 387 358 792 745 411 684 513 356 1225 720 425 1038 750…
Output: 506332

Example 2:

Input: 2437 -249642 400360 -374261 94780 -947892 645794 -104838 -920180 486694 -537471 -918006 203955 230360 -41741 -43310 387620 681922 543404 598102 -551700 720387 301678 464308 395472 -539479 834692 -814157 -124196 121253 -729863 -378289 -831215 859854 251490 357810 150938 -369601 947090 90234 -243970 -690477 746405 -223125 -719482 96230 382149 173348 -375483 905068 248174 -695870 -466434 242260 813960 -118272 -916057 103966 -922092 -45546 -154259 -998606 670029 420540 867925 345606 388574 812736 -340047 -161047 -790406 -521792 -750604 -450053 192375 340382 -385053 371497 -928440 -573795 -669021 -551138 62618 -505913 425494 -580507 -67102 758040 885059 -227468 -812357 834063 -105149 341154 405265 -408113 -538723 -831342 399320 -995861 -606042 -455535 -65054 820508 499327 -794149 -103770 723945…
Output: 1444339

Example 3:

Input: 2503 -132246 -752354 284306 513612 887697 -858870 -230293 -538830 336123 -602744 459380 -671291 -755368 955972 186020 72754 409373 432752 -557887 922841 973842 -64992 -885143 -385858 261856 143032 818521 982878 -921561 749548 -724845 556187 -933609 696445 952177 -80610 -598030 -391008 11566 886849 78510 -895456 901597 -83514 -19094 -149782 685526 717878 895748 -685635 -905883 956441 -994406 602185 629824 -847294 -720765 767320 -769221 -202159 -280688 -464542 -324698 228938 999864 -138475 -706499 -715009 971733 -58565 -168614 -646181 844033 -177165 -677769 -237127 -259494 -789671 -395438 322646 760509 502762 905915 -26075 921617 273119 -63022 128941 -886095 476985 279017 -399905 820433 -940054 -57220 -399354 547805 597004 523087 -137263 338765 7603 613406 60641 210992 -396747 221036 878586 …
Output: 1531659

Constraints:

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

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