CT48718

June's Indigo shelves

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the trading post of Goldmeadow with crates of shelves, and June the valuer 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 <= 2046; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 1701 922511629 568222208 140568303 492434329 77685731 201234319 459447708 113753552 438640510 505835258 176027923 708090960 303335282 406087 741448222 527109925 557545247 741968731 706099593 458376222 839157706 734555368 126824234 322595277 133447096 738340640 386454307 598678104 3212142 468144866 213424563 772206018 822841788 259454696 406675338 717621284 818032840 780461641 493185942 925017951 253485890 503318715 214156382 156344082 391037196 607846654 398950494 988396131 238486664 969536116 112007106 150085511 610513862 109988559 12926917 571976655 466710841 275265352 518644544 26849237 486730424 760663358 703927547 312427872 248646207 549503039 792710226 86304867 81914244 188254823 631730837 566001012 255699671 578991292 186877469 914927088 18667189 203298570 177693757 186492481 156070…
Output: 717092

Example 2:

Input: 837 964052909 892200341 471921431 892618573 235458211 249123535 910715497 602691328 278422203 361625141 406465589 140791791 923216725 707699064 802149527 679948380 751907691 139267163 921493354 315463072 170664268 763129385 803585173 3839105 876622161 522102908 386502250 56350656 557808059 883017908 36951014 665027346 896039383 417654824 867462899 739283548 584500226 213666560 298241218 431090296 310431549 725131674 236391127 949136122 440003341 879002820 274603270 355975394 191602320 914515128 525024450 326113622 827076366 972166215 323702043 835196448 965330950 307532860 280110149 242131533 751187726 412106481 454857108 248537562 787185141 90654918 361188963 342310407 359537892 879485610 183192623 812075275 170263645 39591623 374466818 570740246 917060403 94509632 307050569 781068940 552…
Output: 175633

Example 3:

Input: 706 305398384 279171380 427156964 986009142 656194902 763448412 128142232 162384500 324474125 619044449 354491351 940014633 661248319 377713555 345506697 215336616 859217014 159238233 419983397 437734626 402300110 260118742 751856065 290237962 883769965 484518854 80059825 169576838 835261549 182840515 106233505 844887006 450128806 678381495 948289042 923321839 71656909 825928826 84709034 989803174 550758027 983872497 893195625 497592954 934555601 486470567 642287908 109826985 800347454 696009355 569234179 957801769 607575631 189352400 706183311 236517698 363851667 68407297 511198513 355040534 348938420 688939037 536143740 881178877 219847163 950773355 342152274 738729014 109791674 627040268 197909621 937133241 689041632 460758762 147412334 352092679 227997764 985431698 983449507 312044165 …
Output: 125642

Constraints:

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

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