CT44726

Tanya's vials Reckoning

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the floating docks of Skyharbor, Tanya the scribe keeps careful count of the vials. rebuild the damaged itinerary, every figure matters. 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 <= 3015; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 451 201 297 249 180 165 27 15 269 74 438 76 410 390 322 414 68 173 45 125 350 300 127 205 351 432 130 408 386 221 155 75 62 159 450 51 219 401 237 433 41 79 40 293 385 184 304 349 353 198 3 431 370 43 295 183 67 187 238 175 122 381 25 126 164 357 88 369 52 359 77 423 233 188 347 403 308 203 259 416 211 328 264 6 170 392 208 235 415 176 161 149 182 48 245 367 206 287 57 399 257 36 372 153 331 224 132 400 9 214 314 194 148 340 213 156 107 113 60 419 236 34 143 167 101 270 144 377 354 160 411 396 108 316 294 66 262 2 326 56 325 398 348 291 215 189 252 19 412 253 192 306 371 302 20 39 286 273 210 53 305 11 366 229 64 223 280 256 18 360 179 320 218 394 5 30 50 63 409 315 329 374 112 199 434 242 247 312 441 225 267 103 98 243 289 32 439 157 284 298 382 335 226 136 120 346 330 196 209 99 227 110 …
Output: 50823

Example 2:

Input: 2179 997605569 669593289 743930962 215285499 644149478 990696060 428480367 431968715 605552570 320774907 787422101 812387134 174741162 683105185 290035043 77099015 573336240 574673480 284023278 848768134 918755532 38631246 807766149 521407420 889367365 941283543 490711929 766332239 407478256 527826055 748498026 21381523 327675304 901648454 905929001 223183313 799809519 467281220 649587904 22212208 669829676 292932843 887117200 620876729 192461916 996130605 117323004 999272984 479818721 376081561 358339507 511802000 553737436 284195291 804934267 705785158 414212053 592051341 946891649 273368759 568270985 823056589 461799216 110981656 558216629 225350230 277859689 375268624 986231833 329906285 107629416 229264308 250298375 541181002 856960284 568229404 292907194 530274442 810465163 200043303…
Output: 1185545

Example 3:

Input: 796 749273980 478516816 898712686 935236084 898486933 882653140 816267105 299819896 641851614 536315928 776185657 402073108 601941959 497418951 454079924 920676558 288678044 240548586 730090773 427810025 961017544 324123698 30416293 109752466 410278184 23813539 848607956 503357806 522009643 118333117 776803327 605510690 641435943 244691021 67251312 519945659 111860878 680336567 23980999 607850224 460454846 687527264 758191623 228601832 62181373 641983138 609595771 449654484 682780522 18794504 167242124 510638188 187934640 59839530 90246793 271372318 204305704 922297100 237445310 844008435 145767456 674531554 890392121 103168625 278203727 450122831 173838781 500060028 934699439 1897403 388501230 991168181 287529562 794423272 921210441 458032798 669547490 393031897 466092530 245607076 299740…
Output: 161884

Constraints:

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

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