CT50840

Jeweler and the Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Jeweler inherited the greenhouse at the terraced vines of Grapehollow along with its curious bookkeeping system for weights. Time to make sense of it. 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 <= 1234; 0 <= a[i],x <= 1000000.

Example 1:

Input: 739 508861 701917 513001 106421 308587 263993 449080 957712 921537 631728 897603 306785 844406 2548 32972 665559 795263 490796 622639 105551 755024 850933 835917 338473 253077 824146 704731 145112 770727 714922 702794 277809 843380 547950 983647 376715 152670 272636 806613 364083 714581 137025 365949 277986 685403 681458 536540 458088 815508 727973 989214 76243 718576 99984 885882 890302 320668 453683 946883 774966 123081 962852 876981 489046 468973 37861 492902 801542 895217 246336 771758 182616 614540 867160 196100 906284 384304 865875 68782 762267 753008 766357 565175 714433 787607 134946 407193 484122 338091 759546 959748 386381 822822 306934 483070 67509 135796 118418 397913 458358 437584 314158 630054 370816 973315 502591 851790 935015 772934 175972 583081 701499 37967 203548 612770 …
Output: 140437

Example 2:

Input: 356 68012 635838 814331 496281 288688 59087 421525 148192 284536 764703 803015 612272 326762 144031 903115 435677 368268 910929 16457 204387 894335 282272 917348 538876 421856 570717 732398 815139 698164 546341 315256 221051 952109 448627 688298 476324 399744 253876 65165 597514 578536 587501 505713 387478 96490 286312 599307 260362 952286 582107 698407 176679 682194 869201 137942 883332 287363 515350 666223 396770 748295 125940 888608 451180 722819 992872 624880 773049 233612 392216 272992 633035 655774 449898 507566 761789 740857 946212 308918 233006 490903 807524 886928 477740 911873 852759 418906 553428 25803 473313 527266 999763 976089 477669 448493 427884 637473 283904 533833 691278 303603 452448 966634 53293 561063 31067 319759 906161 806471 509817 109540 260435 948382 382581 643021…
Output: 30358

Example 3:

Input: 748 644 103 8 288 186 477 204 530 732 88 240 518 36 579 646 433 447 9 226 510 381 72 364 112 729 444 399 467 172 677 0 611 252 236 717 271 458 48 95 388 691 342 409 96 459 291 680 219 26 69 380 328 331 538 735 615 653 435 312 35 698 68 620 522 745 293 279 101 2 507 436 496 652 466 564 627 445 374 486 571 404 584 176 214 308 461 199 545 32 604 303 395 162 587 1 718 42 213 264 363 491 314 274 601 609 560 212 372 193 711 309 210 378 746 148 317 83 202 250 631 482 540 23 310 618 471 152 200 526 630 325 370 242 533 454 144 93 11 697 77 244 430 246 7 376 525 566 519 286 441 558 581 53 700 65 424 262 358 4 34 639 367 737 419 663 637 714 479 546 446 550 612 443 227 664 40 634 511 171 86 38 605 296 524 706 397 401 5 548 300 640 63 505 407 253 572 31 369 406 231 282 60 413 329 720 188 44 318 129 730…
Output: 134882

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Jeweler and the Disorder Count - MEDIUM Coding Problem | CodeTikki