CT38168

The Shimmering Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the beacon hill of Lantern Tor. Herald spreads the shelves records across the table and picks up a sharp pencil. 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 <= 2557; 0 <= a[i],x <= 1000000.

Example 1:

Input: 745 435 676 265 376 333 454 723 89 711 175 331 249 641 84 56 283 468 517 140 77 368 639 680 744 207 351 343 467 525 153 423 321 332 462 263 322 159 12 714 127 50 624 73 71 473 35 29 557 571 688 495 221 7 610 415 627 325 22 433 512 681 405 597 55 530 667 598 592 536 388 239 228 594 14 629 216 154 382 713 353 51 87 559 255 561 491 418 400 317 522 24 346 501 562 533 601 565 180 122 111 301 503 520 710 547 664 121 401 671 162 589 546 728 293 499 581 311 579 683 303 26 456 703 273 699 218 227 2 429 510 672 229 573 521 358 421 174 201 48 85 390 44 300 215 425 389 427 615 632 354 476 586 344 316 98 717 246 259 68 735 716 443 502 609 574 590 240 614 369 441 743 11 230 481 472 242 545 125 500 134 34 460 665 702 365 277 359 474 657 235 8 244 295 432 204 46 18 179 310 732 416 135 203 582 554 463 470 …
Output: 138482

Example 2:

Input: 2335 857 1432 479 1563 340 2303 829 1293 226 99 1366 2026 517 580 2187 465 2167 105 1839 1404 2 1559 713 1943 602 2131 1083 1797 562 2230 736 2062 306 1370 1106 1781 56 1597 998 2166 249 1568 2037 1792 1552 380 1307 319 1766 2159 1718 313 1925 1810 101 1430 2297 897 1639 896 1833 693 172 1406 1389 2059 1281 22 2148 1802 679 812 1889 1072 96 275 688 888 1230 477 1656 641 1660 2188 842 83 2098 397 2287 393 80 1698 1588 1102 712 1729 1853 1423 1560 1539 1574 213 1075 395 474 1318 2169 134 551 817 2106 1670 1637 651 158 1209 835 1104 1367 607 33 1966 849 859 1141 666 921 1997 141 678 1238 1746 1157 128 1375 1610 1339 785 1595 1812 190 446 1205 378 1713 1675 1080 689 630 1024 1892 2277 483 464 2300 1836 1446 763 733 1090 1498 1857 237 2237 272 337 1044 452 1607 1282 779 62 251 3 1210 827 1771 2…
Output: 1382049

Example 3:

Input: 836 195956 249328 182794 42867 315658 308471 687581 291364 537897 40242 141860 777939 408116 128739 93399 945198 8253 721398 229745 919098 898628 386780 563057 152750 459465 330754 215154 373761 235096 132279 59868 58902 373285 677778 767336 511113 51918 164327 639360 461473 7584 789093 209394 12492 181241 253863 997026 965246 224631 881555 627112 340016 897900 816080 948878 359216 914268 753363 676644 368594 140638 315196 643746 257965 742199 78155 693085 302389 27046 548408 228506 632875 358931 584119 794395 918574 356147 168767 835664 76800 627557 691812 906392 330067 122934 882098 872022 337362 783745 667910 503058 794320 7281 984265 729080 191265 425832 591987 405808 660968 144739 347991 395067 826050 251975 749742 889119 853817 115661 657885 287672 302347 549920 776858 532991 735955 …
Output: 168178

Constraints:

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

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