CT44168

The Disorder Count of the Lunar shelves

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the zephyr cliffs of Galeholm with crates of shelves, and Mina the valuer must account for every last one. 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 <= 2632; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 282 300338553 191428188 235433447 667482837 616894737 308695366 598666235 367322671 635935574 816195932 618641911 625233747 125774277 397472327 210949397 107687425 871969926 90235791 200008568 853919820 599006125 86880921 666666853 874209407 531447531 227314412 939181407 407306917 998774927 684653926 450901761 328773968 968108779 655474012 130716 78866616 168980055 416818755 134730460 259483885 390540820 92021841 466609939 93228427 959486888 829561959 437842820 769382812 77638981 317338472 666209646 689099045 537926660 934218560 178584622 377570839 857098578 867477229 937663487 553518245 10944277 991090293 139040060 123193364 460838562 380512109 741688949 448161220 139540481 671072934 187517741 301336244 870236646 192222605 102849403 157397319 495746894 101229117 839065741 872759451 813957…
Output: 18139

Example 2:

Input: 438 171 4 371 301 25 165 33 244 282 139 380 39 338 305 267 168 312 49 42 342 146 395 83 55 182 429 367 90 284 62 320 86 174 253 263 141 8 309 401 411 154 148 140 421 44 17 286 138 198 59 220 283 373 331 77 43 31 23 311 248 66 265 326 348 53 27 259 218 58 435 172 308 227 127 183 388 71 210 136 266 356 50 187 34 113 214 430 191 181 120 119 56 329 89 19 155 104 57 189 426 236 251 13 292 95 29 327 321 82 74 408 397 225 106 213 52 436 281 114 133 208 334 223 51 14 273 35 16 237 406 94 335 0 340 384 325 143 276 304 68 339 352 78 262 375 11 230 387 409 10 205 151 75 162 389 194 36 97 414 410 355 351 270 232 420 381 221 70 188 379 322 260 252 344 350 437 264 412 358 400 195 209 330 164 178 254 203 299 233 107 295 161 76 145 307 378 5 46 368 184 289 24 337 156 92 180 6 345 431 423 122 238 134 99 9 …
Output: 45696

Example 3:

Input: 410 309196359 389493036 179048089 537153089 547587991 117606042 291347129 335198571 85562956 382848490 352036130 358588938 140057766 792540172 577335607 335431712 357028147 628817851 101283802 461920216 329552647 674042761 758511612 309113063 94871884 909909137 151554059 850155518 608401525 237054131 343118269 170707856 948696937 80939223 121643690 790437714 925720224 323138531 207249866 40069186 280478884 143384268 418756218 103675327 795445516 768067085 531319938 23690001 526581208 673236711 645528799 410890558 224900401 713339678 194423898 588442002 590595166 476663869 998140255 907226646 595243496 348993906 405789453 87039334 50599586 659887808 808986877 517355017 885413535 734807031 69976904 514502312 918004145 458021279 709573717 216714604 144574155 708754865 689836034 438135915 2553…
Output: 39225

Constraints:

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

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