CT47858

Tailor's shelves Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The store warden Tailor has been asked to price the new merchandise line. On the desk lies a long table of shelves readings. 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 <= 1497; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 116 355158223 399454421 216470046 264208706 308763486 986514185 650984982 259314676 593367256 411304945 27287309 215840397 624275701 122320298 186495523 300924648 913970240 744072849 527540534 327301344 778430699 229991222 161616716 989931995 298742759 987545128 693394066 853649758 221635178 760134356 802293831 610046499 738209187 392282009 410003510 242419466 421392995 41493656 95960327 157014579 579268697 482556052 369438872 640391814 3320106 684738502 883293707 969066333 235369930 10792061 357323152 882292873 139377356 928870439 771014904 90197089 639305530 273274220 193182457 555829621 815008947 999348548 274341950 164187227 357295271 12033081 86679422 892841125 263373392 692085822 869016884 721348199 961067275 814940871 350172919 223599528 552993188 625024113 964056673 504839421 19258…
Output: 3240

Example 2:

Input: 1102 1009 508 414 843 983 98 892 769 91 161 240 1014 159 863 26 215 1048 825 904 20 241 685 434 52 370 777 893 403 721 778 504 216 1086 689 696 695 149 164 870 230 738 992 588 322 1040 543 942 853 460 837 82 171 168 948 382 99 88 879 523 389 951 239 633 644 655 880 271 203 289 631 799 971 476 380 881 473 719 352 455 1002 100 47 220 123 331 873 574 946 250 484 848 494 1054 338 1070 913 586 471 138 75 758 38 774 469 349 552 540 821 748 596 58 502 912 277 198 567 542 118 204 597 398 965 985 626 667 509 299 802 931 184 320 156 691 191 452 975 15 122 614 657 376 565 634 1098 287 154 566 737 1011 61 345 354 95 120 391 244 359 1090 480 968 342 399 396 130 60 908 815 612 501 804 974 237 172 660 646 813 477 104 787 593 400 510 319 423 1026 1061 169 632 808 139 609 729 741 910 39 1036 771 916 575 72…
Output: 309804

Example 3:

Input: 1455 350398934 417936406 292145424 789203366 961592798 480658262 834874631 192080577 252139203 702627036 239730065 272782288 634803837 228206795 610367433 268017745 157802300 64315389 845346655 429195922 518598609 804870635 848976137 784201474 507343753 105183769 24435503 202657120 363242632 970672622 977373732 553852375 25333031 868755329 494067486 553817728 757781999 181173071 15353848 997741387 32741392 96750107 592673756 440599518 920969843 230488077 10448965 439088528 246344812 786280394 492960329 808480100 432903003 324836586 369501496 719855125 248864512 346323719 30902268 771248857 578643330 960179517 492355310 509773238 201720450 480188515 4853066 675199884 759052352 105117881 475235736 8798991 541010281 69745247 97130396 444206685 719868778 587093843 443725983 471788944 604879999…
Output: 521744

Constraints:

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

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