CT61469

Elsa's Ledger of registers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The harbor bell rings at the gristmill of Rye Hollow; Elsa weighs the day's registers manifests and starts the calculations. 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 <= 1782; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 1596 556395851 631953024 798208505 986861111 729644790 294204127 744762396 175298117 901978024 754898340 170944225 385505751 791109124 780274066 796451343 519485524 329981742 111459446 971333425 906117585 891246134 676867786 706188843 623912031 980308520 750330540 671281426 140867958 603589137 200417063 469400921 31873097 589218554 462671778 134729590 110785402 388203662 15995769 319475711 290403592 913180156 337478592 897967206 344277122 808088254 199583695 148487768 991877843 621592395 696709593 199394880 459359108 907435588 179863337 270125952 412281504 50929760 710797152 952763154 945542558 778762631 594330658 876576650 266210725 405004644 729890066 184302502 258334737 674352330 708731479 763313381 948304065 572371757 568122101 297576656 458420769 756683990 622900400 351442092 81580703…
Output: 672032

Example 2:

Input: 69 21142830 609847358 96592880 695282936 707044951 272681371 669675772 17180669 802623592 667894990 325198645 20760828 432316810 717824638 454098116 617856368 977544798 349971455 193982415 450475990 531694775 284235200 567991078 403743496 2101547 40716711 229173960 517947249 899154487 979189662 914064691 363265943 466465680 297120079 428570326 687008509 321563550 785934032 156046791 103514887 353038720 754475293 263475656 632398002 509149299 18993974 140902564 367357571 710708622 158882151 991569666 106506263 486696592 241410951 448759942 135466624 419662802 538736867 290914578 715995715 183130106 104833120 252640956 212781750 518263506 752593192 773081138 89543434 711782538
Output: 1213

Example 3:

Input: 1063 590860549 278738208 78227664 743648966 683174292 367554198 322693099 773846540 499380097 189002454 220925314 94768440 16484889 786331995 60108953 57381607 755266427 34931499 76774357 104000367 835830517 783287318 342512603 757765526 332954695 889822219 7314254 917996597 297370281 812338522 401782199 287803191 800976861 853102134 666681453 145456550 487367304 872491678 814353679 579201003 72851087 325370926 708500179 916129838 64055386 451358057 752679811 249932369 522867215 730080344 556188631 298927430 251188618 452199104 356875190 550956013 711593089 292378628 280079740 314310556 388980521 495135333 207449087 678177045 587814007 702996262 213115778 736489943 15817569 32631601 794520898 507813277 915386228 400277810 412045396 598649476 784363962 902662905 72173914 132600730 442076115…
Output: 283784

Constraints:

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

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