CT61174

The Wild Disorder Count

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the old quarter of Brasshaven. Brevin spreads the registers 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 <= 3969; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 3471 19682393 182626567 445052739 75589039 204155540 612030711 914220369 760223633 362736886 471638152 690459500 427347895 451120943 26780 30686392 214156854 271179079 351881407 156660320 210415755 327777758 783932718 259162083 291067369 87472150 956182992 526726925 110599237 881637507 140730130 322074713 952840886 20505545 301667938 636819934 281406897 879784910 683061348 516618642 616881807 474517429 374643023 617752172 699602809 454862012 228532471 529025040 404103128 376311157 268152622 607068153 290175121 560883320 477557468 628036712 14142231 95670046 263861452 126931531 419020097 998360948 499526284 208331111 397096828 94105623 366895891 406629376 978189194 408298328 34894435 225498735 83440449 989554023 601240746 485209283 411122611 618800871 906013081 476900484 293913976 868298589…
Output: 2980417

Example 2:

Input: 2550 157856593 344664687 320898568 420182575 894131678 707591854 168558951 211693176 868441992 153682192 983307799 141809621 412094533 947220017 211383475 832089008 211166805 144544340 640331124 348592246 280168641 970475447 243881845 312781452 143577850 712966137 761151509 614237948 881222103 969872520 12466446 232759858 776086433 45938243 807192667 586024634 621379759 131972669 623779848 894225930 556793027 282976719 838115695 848013483 944943104 37956210 831902879 578021381 804867513 937835053 163350093 477438625 140796646 705718574 536031178 342701548 716794195 794816855 331304528 415309974 695835996 35764261 73786771 785645763 643624478 176130684 608707737 426437675 776978362 709772409 78567622 576293571 423363323 652190205 928092532 686466891 513838628 322868810 147172880 916157793 9…
Output: 1637020

Example 3:

Input: 1592 961082803 858346997 195795009 167466156 381379168 841343969 418233380 535169047 766817444 97586309 944665252 395071542 279907285 450257728 374732493 451765265 751277855 780228932 362626719 49474237 766627887 833294066 782148581 285737350 771479553 798712115 553201181 511569178 755487976 588928360 798848851 847564154 653480226 259994998 563286075 611159441 920958912 247698905 681633757 730259336 105023302 609787749 584088131 130628566 241877056 201035681 438250275 24702269 319583155 200870726 906385638 20071050 983634522 155651277 776371965 489701174 894365464 390087208 832389570 561707722 487880651 981683067 98638141 40164086 12202843 402458463 583189573 567794841 989844013 719095385 296780526 565681226 598883241 265942174 503946679 98248433 317070457 294578000 218603246 616545058 778…
Output: 635576

Constraints:

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

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