CT35672

The Golden ledgers of Boris

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the garden city of Petalbrook opens only for a perfect tally of ledgers. Boris means to find out. 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 <= 2881; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 484 159 14 423 81 107 462 399 407 258 119 341 193 186 326 188 60 223 67 478 83 354 76 304 263 349 22 17 12 211 57 97 236 386 344 36 362 79 2 251 167 456 241 446 226 43 169 147 479 338 95 158 190 184 99 396 120 108 56 242 220 112 104 332 303 319 363 243 249 370 299 65 41 66 266 89 256 481 292 425 210 330 191 209 298 403 52 395 85 268 92 254 196 476 168 275 34 82 94 160 442 277 128 7 182 123 356 178 118 367 355 260 32 140 264 31 405 389 201 455 433 373 121 129 447 150 269 16 155 219 413 468 412 101 271 331 316 302 115 162 175 377 20 374 195 457 440 234 416 90 278 414 288 33 323 142 387 429 84 48 248 364 145 337 143 45 8 453 171 444 197 153 19 172 339 218 59 122 132 133 250 61 37 137 38 394 163 69 333 173 93 280 452 106 235 283 9 402 86 131 371 448 73 436 238 480 465 98 415 417 483 391 240 15…
Output: 55408

Example 2:

Input: 2597 -200708 -628968 -720013 849654 298384 -539081 431129 -457779 -751337 947884 -913392 -989477 -351789 141135 932553 322442 846887 -321134 920752 -246331 443351 542285 -372447 640681 -133905 403906 114089 116531 32251 427995 122581 -887001 -47044 -558878 348873 242415 -162507 826783 -73480 22246 -994810 -738692 -748321 -822485 931789 -88809 -747654 659012 -702223 270805 -402186 529873 -717846 810565 -151953 -933944 116242 454015 647002 354823 396894 840596 261244 -675746 -724861 928757 -664631 211925 430563 -173868 -489305 -823733 384390 -983672 -954395 -346487 -331661 -299915 442047 712870 657409 393765 576522 -649444 79862 958360 -177611 -943280 146473 475933 -500150 727080 -799878 903367 100033 -498964 359325 -461909 -257154 -846810 153107 -62408 -994009 229989 863624 969129 -421248 8…
Output: 1654681

Example 3:

Input: 730 412 430 571 232 316 587 647 449 148 538 364 694 598 231 584 600 86 415 531 274 134 423 138 1 318 190 147 594 679 724 87 537 646 381 99 626 652 10 345 457 18 208 159 294 482 337 48 655 252 690 12 74 575 658 490 503 619 693 178 696 388 456 240 302 36 670 384 583 192 209 474 405 359 242 182 507 256 132 637 553 475 222 516 78 265 607 303 283 149 590 331 45 236 98 623 609 51 725 684 520 145 433 230 666 547 400 682 413 177 270 466 493 285 254 260 498 468 26 477 540 512 137 273 173 88 171 211 350 700 574 96 686 53 322 570 108 701 63 661 383 238 562 530 174 196 50 194 665 362 481 272 338 455 487 611 161 156 685 450 235 556 476 439 79 651 448 543 678 591 489 533 662 714 418 62 227 282 321 197 610 310 234 151 253 632 11 223 123 131 30 262 221 95 198 356 315 237 233 117 717 557 23 80 416 563 186 …
Output: 133899

Constraints:

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

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