CT61367

Steward's Ledger of vials

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the gull cliffs of Screech Point, someone must prepare the winter inventory. This year the task falls to Steward, armed only with the vials 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 <= 3846; 0 <= a[i],x <= 1000000.

Example 1:

Input: 417 299 21 396 108 322 254 239 357 395 93 255 177 199 172 127 36 162 292 270 249 246 242 50 91 11 316 34 66 368 125 268 301 175 188 386 194 148 399 29 22 107 310 327 353 147 176 320 315 330 28 56 57 130 6 314 216 192 100 233 257 355 401 339 271 41 238 303 179 232 400 403 205 0 397 54 44 185 145 263 115 302 39 155 73 184 48 319 388 207 10 208 55 206 64 96 250 217 317 405 392 300 346 237 161 291 150 343 412 391 365 286 335 138 289 163 38 298 129 113 69 276 288 229 215 195 323 280 293 231 25 362 376 241 88 149 45 102 110 35 82 224 62 124 223 37 58 106 294 42 415 307 116 281 377 240 274 70 3 394 18 381 27 122 261 278 411 132 19 47 356 153 104 186 414 83 26 105 16 273 72 347 154 416 253 159 86 260 360 23 225 266 406 410 248 68 146 341 385 265 136 201 76 94 90 334 33 367 219 235 269 173 306 151 …
Output: 42721

Example 2:

Input: 379 465718 962589 460022 973040 487920 850768 570113 453076 373695 84410 835603 884161 358343 258084 825917 629315 792614 670146 681381 799074 687379 762879 584062 564819 529857 266267 437991 411189 587060 919056 198999 459915 429683 234977 851106 423339 23381 125588 995144 834930 351279 955261 450762 644481 829609 365135 313657 840010 424984 4375 818614 861544 328894 645304 904542 906057 215784 576802 30909 595416 597669 157734 632516 736132 364055 234252 291841 353127 541287 282353 766275 987148 366000 805326 560770 571178 295495 817665 549166 653093 255627 169487 519538 538132 601410 725027 939861 634653 296752 479124 908667 367148 904354 73079 287195 633363 433466 595763 626035 65589 830614 788531 742298 988424 858699 297169 443267 933932 113882 912803 51695 338121 407624 967457 549986…
Output: 36946

Example 3:

Input: 1005 80 516 461 561 782 15 279 294 419 597 747 310 352 756 893 783 261 363 867 448 19 253 85 49 451 536 529 136 422 531 654 919 853 571 468 111 153 73 297 741 515 178 563 924 564 553 923 313 556 227 608 466 729 184 827 320 793 188 436 901 897 998 203 680 743 349 65 534 856 287 643 479 754 236 234 799 221 770 622 762 218 277 722 68 615 112 472 857 416 268 876 500 627 715 439 864 703 521 598 96 963 151 351 503 475 739 368 773 175 250 532 410 635 676 764 549 862 39 502 836 10 60 338 342 959 137 362 186 637 259 936 199 62 698 86 91 685 429 552 930 510 192 289 357 81 906 590 481 968 559 127 603 126 701 356 334 14 554 587 198 970 665 613 196 518 581 428 697 791 404 11 545 948 381 336 240 319 425 432 933 7 168 23 243 752 409 958 891 247 884 912 647 714 273 986 36 711 632 492 257 879 768 228 833 7…
Output: 248170

Constraints:

1 <= n <= 3846; 0 <= a[i],x <= 1000000.

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