CT64449

Xanthe's Wistful ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Xanthe the store warden watches over the obsidian flows of Blackglass's stores of ledgers. A careful computation stands between order and chaos. 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 <= 1310; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 704 593 614 398 174 404 248 637 284 384 319 548 426 617 633 588 351 230 326 443 522 155 692 295 213 225 151 49 466 136 18 657 52 571 243 290 545 186 71 672 569 581 376 577 388 137 644 420 447 493 603 331 551 251 231 631 242 589 353 590 114 513 659 676 34 106 222 481 457 567 477 27 412 703 552 675 39 4 152 346 510 646 236 642 364 544 176 649 695 341 77 502 56 488 500 685 201 434 187 612 278 83 687 224 139 456 179 169 2 540 197 245 378 655 118 198 333 57 682 329 216 127 395 306 65 397 13 369 143 536 421 128 311 119 5 99 427 524 560 336 8 325 515 261 665 26 299 428 627 349 115 82 153 266 60 199 113 87 10 546 433 455 116 195 439 409 81 296 438 316 105 616 93 259 611 400 486 465 66 218 408 394 594 159 538 84 652 260 68 373 498 281 226 626 92 600 63 368 643 602 302 146 59 330 64 517 264 142 661 …
Output: 125208

Example 2:

Input: 1052 745806685 236665271 211200247 113696557 612531096 47503517 816920448 456298860 266249271 954626830 669485874 200435992 984727115 794553362 21673494 912294295 91928820 712405598 532554776 956057082 219870787 691670431 117537742 984883856 437120792 472499115 689661526 876548710 312105607 88513142 436320262 948781060 721217286 274560758 605813969 542932961 332268710 75584912 690385888 406083983 968180649 705712634 395220981 832650363 762030895 470134531 465862075 464202312 450661020 699798790 574371839 593084218 888016642 801674068 449055278 694985988 182141118 442777209 151418446 127751964 795376709 77044292 894730181 93353375 733123249 669732514 353883804 411236118 696298057 466464877 450808792 734841941 117453015 352057881 165023955 593464910 29954978 422367181 917776073 947247166 881…
Output: 275207

Example 3:

Input: 693 404151148 802236972 778150874 697588170 462609770 437499760 707178222 810769137 998237206 832509237 518295013 739819985 194272013 478582632 993044773 191695465 211103712 923594840 768395541 775252458 898898397 391541466 210111992 498976570 365744712 2901805 345937468 493774996 272249349 981153758 980595012 17159831 568618692 183252838 706200629 766687233 883027730 709140020 94653952 556770476 546066 257605810 585130707 614368196 89564036 741058693 39313659 45497775 859052227 142332597 445145677 770256094 710158126 684326857 796943960 30889847 572194911 435253934 301696333 914518600 735226402 431716852 813068627 842053312 170332198 507118387 804481117 481642412 130578021 240822688 211179227 421424333 737361210 893485590 294846649 370573374 703766766 821616816 522912653 410730083 4811500…
Output: 123053

Constraints:

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

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