CT58721

Tanya's vials Disorder Count

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Tanya the factor watches over the mountain city of Highreach's stores of vials. 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 <= 3834; 0 <= a[i],x <= 1000000.

Example 1:

Input: 3180 258864 54875 371408 847037 140466 437529 982117 93982 919989 228428 708729 670402 874625 771045 11543 999578 261754 148875 264743 40790 734841 935367 11444 138470 425527 38840 821652 345907 575436 407758 812836 858856 856510 907831 705258 195691 303604 553184 353745 991772 646576 39091 243348 2547 516787 423557 312345 536724 67733 226787 368245 368920 202668 734576 147974 963835 307790 517564 981691 613298 963726 524158 714879 833486 224480 596383 209344 901257 90382 246679 316079 336946 64906 470079 120435 877235 517845 16294 650037 566225 556145 304868 529597 984878 435190 905958 429737 858742 104721 489418 260235 796629 255127 397055 36216 509553 815833 935167 564814 83841 104006 893543 888893 855851 123375 60011 679747 523481 535013 574363 751111 88543 584415 249351 30684 10387 21…
Output: 2511769

Example 2:

Input: 2605 483464 715041 405102 802723 971166 222357 587109 541309 414317 314805 900707 213667 640823 437785 736406 17675 787078 496609 655979 664177 871088 390405 401643 644682 738464 757451 350663 178930 431601 418236 364619 513203 723701 471850 44123 691892 297500 835252 476175 960993 328579 895562 575902 19648 674105 792914 605221 448403 368011 948816 381446 791720 188497 50817 82152 613504 523196 669240 590725 161443 785781 858096 770413 714578 636205 701299 624188 150403 163570 391923 576560 208707 557595 648074 326240 122458 376464 267354 702523 390096 644326 264003 203817 409243 50559 301807 426945 721114 414715 330481 606838 116277 258649 506276 132257 295486 888330 551140 505600 314422 831242 660497 772394 109530 881941 309909 595228 82403 451928 535531 544132 889019 484465 909324 7374…
Output: 1737333

Example 3:

Input: 3581 163868 863142 431707 97466 790217 323958 870123 607966 442102 83289 533264 697986 223256 955233 768417 376053 61078 308083 688483 986147 358909 353682 395364 742672 187809 455420 848667 661470 552758 622224 747041 553765 786890 665852 92974 805994 322831 772711 462660 965398 397324 866368 746979 852584 137059 681269 198452 427931 806765 962333 575571 113505 415114 778276 439796 234463 99673 633268 506286 147018 344362 52331 131510 557816 20816 443978 243909 221051 916186 204196 600525 400561 544208 149796 634171 610740 787549 458269 52278 636440 940513 485070 801218 369644 932098 852777 901325 396123 986798 687949 433424 977376 810708 523895 222365 801822 161541 512274 476161 259536 588360 208201 22025 773676 974646 900299 322027 625871 159450 407792 644156 297704 704783 303379 477877…
Output: 3179590

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Tanya's vials Disorder Count - MEDIUM Coding Problem | CodeTikki