CT51378

Marble ledgers Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the fen lights of Will-o-Wisp with crates of ledgers, and Pavel the measurer 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 <= 1852; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 1629 936232309 627967085 375712333 58161495 346634566 616943649 708382858 334452898 874465729 451794493 481053929 729300200 525157432 367540534 4414987 372564322 897221900 116784849 793829927 223018893 907949872 476821663 848767349 791193426 39053308 81934260 651608652 825316565 103320535 231665440 821324729 551556342 75669839 237909478 322609474 591236342 545922454 66027032 54390336 495122198 692616638 880497313 981194259 2188860 327548877 980006927 931221224 617853806 719242731 926587337 617275656 238300209 394921305 900660116 859118045 848204086 571285468 776198615 769719523 905443327 668087215 290897198 995215592 182340150 16341515 563632651 786688325 32087593 426793552 400117436 795607427 889412582 539300516 738303650 941859477 4551296 266659840 766523997 833121608 549380612 663921433…
Output: 668264

Example 2:

Input: 1167 308 873 210 905 1089 384 44 965 777 1154 192 104 826 737 197 536 938 149 1019 1046 403 822 556 535 613 734 1057 1128 667 299 396 214 63 520 956 947 697 883 609 773 368 411 646 797 705 334 538 503 601 748 753 903 1093 341 6 934 909 83 284 983 312 940 986 1017 242 124 395 11 425 337 258 20 867 169 621 522 559 589 1113 843 833 760 1142 612 939 513 874 57 1117 625 762 819 486 25 1074 771 586 1055 591 437 216 483 111 125 356 652 788 871 985 795 143 443 1033 1009 261 317 574 1127 860 128 40 189 1084 931 967 1067 181 645 266 782 239 992 534 879 1020 893 289 329 1013 644 142 514 156 257 923 218 353 347 252 703 95 969 1087 47 321 121 856 835 821 481 234 502 913 316 958 390 446 533 945 444 244 1010 532 186 698 891 361 592 902 297 448 616 776 562 541 342 497 685 865 166 916 1119 1126 890 1036 80…
Output: 339296

Example 3:

Input: 565 421 492 479 64 350 370 556 74 138 277 486 548 274 451 559 62 186 502 387 22 116 181 177 488 212 142 309 376 75 391 228 408 499 248 341 340 470 149 270 51 20 132 313 56 323 521 192 15 27 473 462 562 207 148 236 87 418 206 46 347 466 1 433 235 183 41 457 43 242 260 107 55 188 374 128 102 377 234 106 336 427 60 547 57 257 200 77 23 544 71 194 196 232 59 319 167 54 28 269 24 3 250 89 306 231 334 36 111 199 438 146 517 367 411 35 356 61 538 214 244 67 14 528 335 394 381 221 143 295 398 511 551 363 436 276 91 510 339 432 409 129 133 197 343 169 53 332 463 73 251 475 465 7 195 450 115 496 50 227 202 512 330 175 401 211 399 455 327 541 44 80 281 37 430 180 481 497 328 442 287 135 553 47 265 204 40 437 158 17 359 472 476 219 184 252 338 42 385 315 176 542 291 560 446 324 25 21 317 65 307 72 90 …
Output: 76478

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Marble ledgers Disorder Count - MEDIUM Coding Problem | CodeTikki