CT41872

Milo's Timeworn ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the ember mines of Cindercrag. Milo spreads the ledgers 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 <= 1918; 0 <= a[i],x <= 1000000.

Example 1:

Input: 964 906158 382725 972711 930018 868142 838688 13837 485538 354819 642977 307246 84602 155935 540690 865919 363036 685115 575235 812754 69911 772011 330539 963647 345763 784132 593680 762235 513682 988423 673598 267519 504548 618993 935401 324541 980379 294774 506146 113451 538285 186896 555869 340058 197113 65084 146085 693162 483162 789541 576787 50565 28528 672967 759963 372992 604486 394281 239355 1955 864776 465104 333112 699540 595483 545548 859171 483622 105096 206955 50235 316726 511332 46383 900984 751974 968869 24207 741915 357910 216314 652296 196775 915483 881511 88105 314789 270824 721252 600450 581243 588955 255330 342471 734754 110870 893802 176868 582096 284013 143927 466595 482910 667051 76982 403399 747626 436639 447704 323832 160360 219944 167182 62402 875830 425773 89774…
Output: 229937

Example 2:

Input: 485 94 167 80 177 235 87 123 248 466 128 99 478 456 195 223 305 338 351 34 409 434 379 439 73 219 287 315 359 256 322 144 182 461 275 436 134 393 119 117 236 229 12 85 418 23 198 43 368 89 392 4 146 395 300 112 27 42 451 347 387 76 312 61 234 422 467 179 188 246 77 225 5 254 25 65 308 245 381 161 155 298 231 212 348 103 91 437 417 405 365 52 307 166 396 217 11 263 20 372 86 318 316 214 311 399 147 404 58 66 459 383 102 137 204 45 207 57 139 301 202 191 240 444 250 96 306 17 473 252 431 270 369 151 349 358 289 278 470 197 37 455 93 62 153 423 238 291 184 171 420 326 371 60 464 435 432 277 260 200 290 59 452 84 75 111 199 28 284 56 124 377 419 401 427 474 118 309 68 394 131 329 149 230 251 428 267 421 152 193 323 210 406 145 90 353 313 332 299 370 105 484 366 429 221 224 325 40 74 425 107 49…
Output: 59613

Example 3:

Input: 116 976166 646144 738144 213008 589213 221922 770122 393004 328261 753383 219803 697551 26139 653928 187814 781575 448935 706303 40986 671752 820155 956229 290222 96119 807131 593287 418006 75089 661599 870620 503540 349343 693105 174777 77931 204638 656796 818520 815458 899301 788082 956929 416128 727626 559742 758288 850961 607501 900924 334962 470837 578735 508710 938713 115548 190477 865496 219150 395828 975775 816151 421995 215411 622670 188232 584974 615989 516369 277692 284897 857373 605420 22794 318551 496202 63771 382 57793 297813 662588 214940 416485 330956 306756 203846 550002 680257 729237 708227 408689 141591 1733 795841 320517 9977 55200 196694 544314 203649 552081 304738 390634 452915 442711 987973 142152 635337 284716 385937 59631 457864 134613 327347 846004 279476 722066
Output: 3823

Constraints:

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

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