CT58968

Orin's crates Reckoning

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The harbor bell rings at the temple city of Sunspire; Orin weighs the day's crates manifests and starts the calculations. 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 <= 1485; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 609 676965301 656843582 480554722 498890472 168576375 789005804 535705625 302478059 811604066 549377433 359568903 715423446 279327015 606155338 526722616 420910216 281112170 828143817 869279109 693101431 228450610 71335027 923375947 181320238 737616978 563396018 591259032 408797334 209923366 81564166 965387947 862234673 356754140 687670234 713713266 984120397 836163151 707253311 997774038 362215814 907393134 231174362 865029743 409210078 38264902 108640491 528516723 840438682 206449018 33237145 267023894 392130582 215807152 654501730 321588629 634740830 25130128 147489940 12962995 905720871 193805288 42728158 776162913 754356490 621093155 668001269 790706965 560050782 434402583 582623954 429139846 558640441 922217393 366920532 214589796 47864291 686459307 44215938 965127623 991135696 99299…
Output: 93243

Example 2:

Input: 1436 215 377 1303 40 1092 998 211 411 1045 321 531 69 102 1085 1000 86 1380 774 786 1278 1223 214 1196 738 412 95 696 977 602 444 1327 558 1309 721 734 1271 1152 369 770 1263 728 407 280 1006 404 31 1088 939 856 796 1051 613 545 324 563 933 698 1080 539 123 993 950 449 99 954 733 1015 332 1060 776 255 729 491 943 424 948 1283 375 547 36 942 231 822 1123 510 1395 18 1316 1342 1241 414 821 1320 1013 606 487 1172 139 559 717 381 885 387 1371 1197 168 1004 51 173 1113 1049 1091 901 1383 1237 665 803 775 599 151 1410 398 192 549 268 1234 1302 1279 693 854 105 278 592 210 1261 1239 682 1010 1127 338 1072 295 162 1217 1094 815 297 911 485 1131 433 661 17 546 499 1157 1284 28 64 746 45 928 140 203 353 924 337 322 452 310 290 600 1221 274 1201 1099 38 625 1345 1046 154 39 704 517 248 1326 1408 267 …
Output: 509545

Example 3:

Input: 499 103 35 409 334 39 369 256 133 366 332 274 131 94 120 121 172 211 391 160 80 290 191 398 20 452 485 434 188 92 111 215 299 345 168 207 280 330 493 123 320 212 193 482 354 17 435 276 60 218 173 140 178 293 143 21 252 1 124 333 464 441 213 241 484 15 230 351 423 307 65 378 48 278 419 167 197 76 203 356 99 371 150 34 169 427 129 262 301 63 373 89 24 310 242 56 339 450 100 86 346 462 159 135 287 459 487 43 45 350 361 240 108 206 470 440 491 268 314 377 431 478 234 386 141 349 36 41 98 259 204 189 454 106 312 47 403 231 411 298 38 313 161 253 388 136 309 4 436 448 387 282 413 162 385 453 57 74 174 395 446 305 107 83 288 364 148 25 32 365 18 496 432 263 251 152 176 271 399 67 481 171 78 264 232 199 126 393 22 417 430 475 405 402 31 270 348 468 269 476 66 289 471 451 358 237 23 367 455 370 5 1…
Output: 61722

Constraints:

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

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