CT53639

The Indigo vials of Emeric

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the lantern lake of Firefly Mere, Emeric the scribe keeps careful count of the vials. Prepare the winter inventory, every figure matters. 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 <= 1568; 0 <= a[i],x <= 1000000.

Example 1:

Input: 403 846359 173930 653232 8019 896132 994388 354461 978358 234036 424423 37625 802543 894721 862558 868946 112335 142791 366407 92725 381840 359645 619266 812247 353416 180859 275493 369376 461769 616019 310281 82083 870810 159562 942971 374321 877553 943821 566379 945556 893398 356790 656605 539021 198066 713132 987844 466790 110706 623660 444143 201580 820492 549506 19279 656944 338748 298652 68337 160618 941074 591995 206903 341615 497252 291942 941865 101784 46601 956688 333876 67180 401312 171142 339802 787498 447525 94223 492205 416453 206216 215753 759232 28204 842200 912784 152562 835305 535759 306238 115796 540245 126535 608804 396784 166211 674682 227510 315108 324938 865767 451191 518321 28865 661252 690555 169932 457367 915405 522724 840250 185541 662383 264154 949791 369491 216…
Output: 38810

Example 2:

Input: 480 904278 335906 670031 542865 414762 354409 979249 268429 693897 235835 315800 175766 251772 715623 768492 141612 316780 390499 53138 401830 131726 803402 570580 965239 367364 353145 30446 206983 803825 190472 61654 642020 68655 528904 96349 482436 421104 327829 908285 163399 719082 729551 852764 333415 955304 787129 54881 177956 949137 104440 945440 197379 467069 255945 330584 931928 150677 124922 94306 160375 623999 888680 993203 341659 144146 578227 973813 526984 147653 505973 848118 870953 128994 737626 137546 971332 710950 561497 537023 780937 711422 328452 902292 237562 170565 865822 83808 297231 108100 336524 42965 326845 234453 778148 879673 289155 661568 258043 518729 354366 654030 302409 585996 357290 27647 828321 408897 890257 58543 148860 45713 719287 736787 459963 111104 671…
Output: 56664

Example 3:

Input: 1512 165605 553487 25151 165037 254932 625378 390397 505490 186054 397683 988777 487473 310172 814482 697505 911567 5197 151038 635166 647006 232315 829984 76887 739308 698694 392414 866209 5359 514347 686526 867385 192348 665279 93046 619183 889616 319416 402221 847265 860958 651687 390288 845875 777013 789331 412633 69565 282520 256079 374635 997122 167654 821032 699580 220121 296131 385942 267864 383589 269669 851312 961666 437062 652503 274152 561300 323199 208856 699089 787543 821579 609508 959538 334954 898535 372501 109078 925227 267398 590812 467525 868205 410223 946707 488889 286274 676406 699149 746218 951382 461389 323548 799645 186556 433106 289466 239061 659344 15489 553083 508581 436656 947016 92126 789735 295688 542306 341116 495855 505887 635148 453029 20166 364074 698398 6…
Output: 590760

Constraints:

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

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