CT38299

The crates Disorder Count Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Warden runs the cellar at the floating docks of Skyharbor. Today the books show a list of crates, and the numbers must be worked out before sundown. 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 <= 2748; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 859 643745650 502966412 200176762 909396179 288807165 595755307 673488265 398583586 534175385 117781383 879182165 698681635 188983504 151827876 492180389 239867135 625285483 379419754 499936817 544073487 812428832 541721573 235820441 573022936 812747980 747004814 549290902 705378024 451138605 89632552 794211620 966081523 572668553 874522915 945117932 954791255 787165698 500631058 12684388 19021936 312443163 948712046 894047180 274997861 385758091 564361623 133302247 875397061 993189772 916989740 878819950 803484112 854729983 202150504 579507286 951850586 696473292 962651214 348287420 437836281 181479993 669594877 38891685 169668913 630910416 613838587 219163696 458845060 402159489 217959194 824384072 883346760 371723155 622650860 351694794 597010289 477317803 241892260 676719058 259599689 …
Output: 185754

Example 2:

Input: 875 461640367 209654658 618433723 352892243 897714889 107899802 448165939 195836560 368462524 208051066 667425335 45766411 226641166 783532906 68801882 20300195 192637057 300418230 210537511 118354209 46985188 652749352 770451863 213064320 223922597 665385971 740981030 544747 327430420 732381667 84461001 55506812 694076270 318832984 820001300 159083180 384824475 990068765 67203942 407606018 677562910 767942783 22711842 597056738 122283001 430667980 196325891 807640573 856614953 969761325 714910293 738000483 602035806 248011888 274865022 15077295 826418995 795681126 605161721 266052424 912302981 796938014 141847769 765431156 496882408 88379610 159819801 59046977 858817371 914248366 118648771 874770064 384113723 223274676 492731234 725689370 319785425 45466319 487732379 492645990 411567749 6…
Output: 190081

Example 3:

Input: 710 221 667 75 449 701 659 176 552 648 412 384 48 23 61 410 59 52 565 700 445 337 639 246 309 256 125 348 418 199 2 301 640 84 576 338 80 606 490 532 324 163 674 175 164 62 89 126 117 171 361 683 440 489 459 297 409 223 421 72 452 570 510 71 376 145 507 438 623 415 687 98 228 638 520 485 493 352 618 680 50 254 189 601 257 647 429 407 173 575 554 688 495 68 463 367 349 681 306 529 336 168 522 238 162 572 508 227 577 615 268 307 298 461 160 218 296 10 292 505 423 480 31 504 167 669 237 424 94 704 580 118 17 627 323 705 45 242 255 353 29 129 245 387 42 44 195 571 15 646 366 347 534 543 587 214 390 18 276 157 454 545 247 184 598 476 39 502 166 634 26 283 521 531 243 119 253 200 536 685 603 34 563 377 453 538 455 608 339 287 79 708 354 484 448 425 153 698 641 398 331 269 427 249 155 49 341 170 …
Output: 127437

Constraints:

1 <= n <= 2748; 0 <= a[i],x <= 1000000000.

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