CT61698

The Disorder Count of the Twilight crates

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the savanna camp of Amberplain with crates of crates, and Mason the chronicler must account for every last one. 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 <= 3719; 0 <= a[i],x <= 1000000.

Example 1:

Input: 2452 187 1109 314 1927 8 1939 2399 2038 2154 2013 1021 1441 2220 1199 876 41 1936 129 1328 109 1623 773 799 228 2120 2235 2131 1408 1114 355 1847 1667 1285 1870 1905 333 15 2295 1610 2449 958 1694 1518 642 327 723 2041 1213 1777 1804 855 2142 648 847 807 995 114 406 2274 356 3 1572 344 2386 6 741 1972 2096 1906 511 663 808 61 1617 1286 653 365 320 2088 1181 2032 2360 627 1924 247 1735 1112 1859 240 714 771 703 2129 2373 2239 1238 1393 856 1118 2319 170 105 138 230 1363 1378 339 1102 1407 1861 880 1686 1738 2363 2191 501 1496 2355 157 2027 683 366 397 307 53 913 584 2309 1257 1326 316 2171 1412 1398 2312 898 1141 1449 2350 690 2447 409 412 1563 907 1611 2228 1467 993 2328 367 1527 2366 291 297 749 818 1715 2314 581 1996 2410 58 1001 1522 1618 1820 1475 364 292 512 670 263 1468 1413 215 150 …
Output: 1496817

Example 2:

Input: 1192 508111 63677 825580 833040 84191 465473 858011 138464 555511 243296 139059 194777 642857 306302 466355 205166 526212 945149 940885 345112 523694 550382 499288 874771 578939 580078 100418 646140 238945 445701 150745 127003 837163 497534 418071 763748 162509 467294 648958 11668 571761 218772 802419 679750 488860 903659 400055 435323 260802 492531 229207 205794 7902 949440 686610 707365 864943 889466 364897 146948 968434 772217 118524 798844 395873 843944 326823 855949 735780 46536 777541 788746 253087 921382 495061 830449 308261 737685 826134 710055 960202 293063 240302 942517 771025 92087 812583 162083 600466 453861 80022 98567 583208 22397 422987 355584 975321 527081 430301 855744 974529 382889 315530 811279 874263 532956 622164 238295 210702 85979 612254 781991 520361 608768 995274 6…
Output: 358976

Example 3:

Input: 1271 582819 727318 829487 841812 72707 126414 395749 858760 628027 372408 851680 959184 876239 999450 130708 977320 242773 516463 737682 384316 843569 131274 367161 555645 753701 459367 877662 783067 303397 290609 149059 879922 104311 854566 265472 396558 112868 246913 641957 797733 360917 496314 425424 532843 288858 331235 613236 999483 983634 13429 282270 665922 606289 427545 492617 340119 74305 593079 470061 102651 579848 467574 63373 821103 798588 685467 894823 909092 887783 203986 956645 532708 114557 746629 581865 705941 879905 972016 186493 165064 963781 814791 676294 848433 360040 607861 879843 950023 52431 210082 226532 114334 974150 620207 317718 81350 775431 435377 970224 968872 620536 947730 526475 566633 304478 162071 363987 872639 946348 879338 719705 626168 376812 444799 797…
Output: 407107

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Disorder Count of the Twilight crates - MEDIUM Coding Problem | CodeTikki