CT53921

The Disorder Count of Ironvein

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Maya the accountant watches over the mining town of Ironvein's stores of weights. A careful computation stands between order and chaos. 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 <= 1181; 0 <= a[i],x <= 1000000.

Example 1:

Input: 456 804216 62267 883342 595447 238576 215762 647471 420142 156169 420295 632476 505462 686084 37432 731445 799038 912313 398236 952473 163639 394419 350971 864412 932673 565399 760763 389257 438266 671225 837504 139340 435931 933672 538838 474224 748746 792679 885338 301788 330584 721835 494331 843982 170271 369760 907487 347809 631839 822521 558027 341106 829856 557879 434177 287250 101653 387050 299764 387004 238737 731590 514227 601758 399828 922724 853132 372689 198332 330270 354713 46553 873539 373291 995985 492074 377779 82958 843923 290113 302526 846160 85794 731846 271077 522644 97898 977047 498979 138439 491321 284648 592560 921613 264182 46373 730268 928277 462431 843823 71228 762795 574195 886719 335030 477116 947462 591294 49497 212651 874114 798660 718286 495063 261583 172592 …
Output: 53184

Example 2:

Input: 1149 156769 16645 319766 647097 833374 660307 191804 769331 445830 536296 552837 635070 567981 111522 751468 694402 710471 997704 174106 83297 511667 962705 142478 834153 818249 558599 462389 23486 434399 119333 669427 5921 461308 809642 615241 5372 128763 751522 536345 206039 437405 127711 584270 958030 925395 885496 434479 305251 965330 598210 889245 446660 487363 77377 256714 308879 442769 511221 580647 160686 262793 328808 562594 333976 946625 15755 990426 474468 621474 179540 606359 13594 127137 919326 630979 75202 183218 755046 116311 487431 532671 967054 847274 703032 363991 185738 342910 955392 793813 129504 862677 587469 469816 847997 101138 352838 190088 506274 186763 583850 493039 652914 813053 621073 85973 409249 948380 347877 854880 973158 371356 895768 325443 319273 91079 131…
Output: 336292

Example 3:

Input: 414 326698 232857 404428 712092 252177 150640 112904 325788 790244 761278 660182 66573 569470 294387 651927 787410 478222 976411 449810 912799 265701 613632 999277 753873 228737 959183 602194 387165 256571 881481 491008 9894 163571 638673 477654 693344 675498 698027 385942 363430 94939 666393 280806 771926 728724 182239 604318 697844 364626 86795 885155 291632 632093 401706 627468 885047 589133 382919 639021 265822 488660 429878 72588 277747 496871 904626 566613 993243 649659 50653 265868 186869 68949 930353 324517 475094 730040 678435 743201 751494 204317 102040 583921 672813 806247 551321 81052 167175 382502 787307 525570 801348 737174 80701 564374 375847 395141 849172 995246 199072 444349 656428 900744 436081 611980 511549 47823 187581 50522 115793 935603 194758 167694 34095 34588 84721…
Output: 41513

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Disorder Count of Ironvein - MEDIUM Coding Problem | CodeTikki