CT50699

Kavya and the Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the crystal caves of Luminar, Kavya studies rows of ledgers entries. One clean number will settle the guild's oldest argument. 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 <= 1433; 0 <= a[i],x <= 1000000.

Example 1:

Input: 47 95924 376848 859811 391575 945406 994934 620849 769338 859260 332730 398188 959729 975173 337130 751362 795183 391092 599315 583198 476745 555411 518395 505864 358904 292298 390116 407148 351237 756711 170389 614639 916111 213691 317741 143546 903763 775903 875231 86429 349153 564441 88835 758205 122904 540362 44963 466933
Output: 667

Example 2:

Input: 506 24 88 13 107 484 380 46 174 435 186 142 319 15 452 182 426 255 45 57 114 21 160 75 9 32 429 106 291 99 252 395 73 428 89 447 402 286 69 227 363 278 261 137 329 40 213 173 471 76 81 30 328 20 140 437 105 295 407 266 323 316 322 441 494 138 199 457 392 14 60 71 339 134 90 120 29 8 401 327 118 210 377 127 299 148 460 67 175 311 228 93 70 4 448 205 334 431 176 41 482 192 110 305 353 95 161 293 446 310 505 154 341 458 209 321 101 61 379 478 196 143 84 217 423 151 6 167 332 135 408 309 183 25 253 303 280 497 260 87 359 254 313 495 112 94 191 198 406 17 474 172 337 422 356 52 124 240 19 411 66 283 355 336 59 444 481 222 195 498 108 453 152 201 163 449 418 275 347 468 74 150 218 178 381 221 2 274 445 244 115 0 279 373 168 371 86 177 374 236 470 122 96 424 425 357 7 249 117 459 393 165 315 79 2…
Output: 59523

Example 3:

Input: 96 652004 368326 309042 606679 900315 262251 685692 378459 263460 46110 90547 996337 295267 43162 915296 651918 360830 527941 143337 386060 660219 305442 398802 833090 95243 440441 946331 622029 164996 697574 9247 262595 242054 872197 315231 473412 118376 757781 492293 765649 225404 948863 302256 633188 898022 950954 159426 400549 416909 134147 911774 239317 359646 414685 614962 335394 664214 100806 22788 439744 738558 82196 171378 464300 131837 820030 998397 98855 658689 647193 115574 972894 843669 96713 311196 726970 742060 228925 210559 876483 743143 939535 477310 648999 97625 302690 611030 976852 389547 61488 187529 62929 511426 742268 810298 465995
Output: 2211

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Kavya and the Disorder Count - MEDIUM Coding Problem | CodeTikki