CT37493

The weights at Goldmeadow

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the trading post of Goldmeadow pays by the answer, and Ojas intends to earn it. First: the full register of weights. 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 <= 1246; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 1107 11178623 940406038 585448684 569828265 628480620 795398715 996440994 414091180 711682482 863367385 643928882 995445582 374683831 944967339 419751214 615335393 697134553 982243122 842121064 268829229 157508900 612957205 591344693 907182219 160855043 83500163 797809020 215222171 373555967 478106169 149826410 481759913 681836449 536642869 703596517 942835107 86754378 502743862 730032886 426983782 550662541 827223746 397648891 652236624 603634330 95262407 960334230 847858460 57498250 143243674 120305986 573171838 853812968 90167217 256820603 623303419 201459681 297411127 925048005 132051665 942258976 356940220 949713075 830311496 687689649 421918266 919579790 312586544 74615170 570481543 621132706 61936563 197405630 95770135 188785224 604941427 233340440 968471184 645797115 375151260 3986…
Output: 307495

Example 2:

Input: 972 341124395 153819567 332291827 514881893 214447550 135775158 369417333 470924946 899042580 962535698 606515870 506115327 589056659 948832426 150913063 117767204 834295814 765745419 181810195 316254748 729626837 594282004 408113266 869367891 375203479 297036074 572282261 268324737 670599059 767484949 969660163 896473582 560787517 781746287 367214215 827662594 687438416 526480859 437523282 329806227 319092638 315944496 127528329 151294864 748456912 676411256 723804801 838177958 230870768 888868705 395933244 403013459 983167116 926871872 602215450 61254223 181515792 915365439 504160373 162093515 737567589 476271520 751442717 732809502 60241073 899249561 537789358 169251532 422926493 949694178 138097129 30915036 310973463 244153448 687893964 164993598 402452219 300871069 621911676 539523121…
Output: 230675

Example 3:

Input: 601 66 163 211 373 554 90 132 183 392 234 418 200 589 144 4 98 482 595 384 317 541 262 370 492 548 214 271 318 170 57 147 349 583 93 364 168 175 68 245 524 319 544 475 596 391 314 581 289 76 447 278 233 493 15 298 14 195 408 527 287 369 390 448 167 149 243 152 491 474 253 515 481 547 361 508 270 564 37 486 327 207 436 423 9 78 439 585 363 315 325 204 409 280 338 308 526 393 187 113 465 316 142 407 600 342 54 17 24 246 277 394 45 157 194 28 96 201 543 560 171 202 279 344 34 584 414 334 348 64 350 72 529 514 433 269 185 181 74 128 273 101 26 539 487 130 599 550 265 399 1 285 534 166 107 221 328 247 12 302 92 252 403 426 516 283 346 372 532 82 231 504 53 31 123 424 452 594 86 81 108 430 461 500 586 420 455 388 431 561 470 119 531 259 235 353 117 505 451 299 224 143 120 445 116 463 386 497 429…
Output: 89406

Constraints:

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

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