CT40346

Maya's crates Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the otter slides of Sleekwater, someone must reconcile two mismatched ledgers. This year the task falls to Maya, armed only with the crates register. 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 <= 4000; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 2441 363915461 544265702 539018972 39737417 581436745 639810427 689623340 715595470 250260274 165649817 422452487 925999205 609063543 851773585 392904745 301231326 419423956 724334977 928456365 752011384 209752189 952721930 373065550 434196744 57461366 965306881 710473424 25665415 391016491 347083296 633726768 883625090 142827463 279558312 722574009 703139862 529637024 417665844 230070294 247938212 4103580 98083883 100359353 74427277 312257088 127846494 544246908 942184417 203829537 743720356 691257783 579470383 852735211 125307972 449424090 843830503 872632026 315337102 904094294 431408083 781557317 511007022 190289236 466738551 254476966 955286368 912037264 35801690 563134068 85397793 250606722 692350797 316749491 904820423 965314825 663551316 317810864 368384387 771224225 880101530 8873…
Output: 1504801

Example 2:

Input: 787 347 711 229 382 74 54 231 364 169 615 163 103 780 140 776 250 677 594 117 113 554 463 10 759 470 407 301 175 5 525 367 73 773 658 352 196 75 60 120 718 778 455 287 131 402 474 598 665 235 785 725 18 429 560 503 401 88 278 198 390 534 739 576 529 267 639 467 411 693 681 41 257 80 661 435 201 380 583 265 734 96 285 524 564 504 289 666 667 85 293 777 696 557 518 302 573 110 753 318 309 766 350 252 67 764 448 339 545 78 623 416 32 396 769 664 674 464 83 561 314 371 76 360 58 168 626 738 400 63 294 471 35 604 49 146 442 323 493 484 472 580 282 292 692 385 152 24 164 214 514 202 608 354 272 232 52 603 571 25 243 81 421 132 329 562 671 259 710 306 669 762 86 322 705 21 670 48 487 700 176 655 426 311 246 644 23 144 137 340 334 728 258 253 315 515 642 192 100 366 617 483 165 733 516 610 546 8 3…
Output: 156283

Example 3:

Input: 251 599305513 494526388 596922902 714777081 640099911 679921072 562559482 435297560 330258020 164889992 455584158 116270516 909814531 732899647 526874416 460034651 132904540 168785302 783992011 640755803 146891160 725319062 409091716 797128595 645220373 198594905 555993966 226369462 705371623 486785615 616029865 797373560 881351969 357604962 104513321 740372433 990145471 36313602 958375089 852049752 27932254 250873230 408146173 801516311 877627395 929290312 54764265 124749276 829599327 745990857 274231656 465466093 552955676 674868936 886968040 984724877 841098715 833483023 248269711 415497439 435269660 148662066 888718481 193294734 109459797 718432959 130300833 561497154 865677577 164390597 752578276 468739831 674421227 955821699 751909821 899893540 192909451 623892690 625055641 287835347…
Output: 15744

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Maya's crates Disorder Count - MEDIUM Coding Problem | CodeTikki