CT51282

The Disorder Count at Masthead

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The registry keeper Piper has been asked to outscore the rival chapter. On the desk lies a long table of crates readings. 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 <= 1113; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 414 366 240 6 18 202 176 283 394 140 413 252 41 168 104 99 109 355 174 1 31 166 15 285 146 251 348 157 67 360 402 388 24 339 30 322 164 97 36 55 141 185 398 135 288 82 343 2 227 281 327 300 70 264 232 12 7 323 390 221 385 116 328 317 145 137 316 350 187 239 111 381 408 53 267 114 336 170 19 244 39 74 401 35 91 338 279 321 241 215 245 193 103 142 406 132 62 307 86 359 228 51 397 191 64 297 291 373 354 122 310 405 242 177 211 326 216 38 37 10 188 278 172 235 119 380 0 160 309 88 192 230 171 75 89 248 266 303 113 223 342 181 136 66 147 158 391 253 333 8 13 71 56 376 144 306 47 9 161 308 218 410 275 377 34 125 374 386 274 69 270 204 314 214 208 236 234 207 65 190 369 182 243 246 365 199 124 23 379 324 345 107 331 206 237 203 96 400 100 84 52 25 233 32 231 258 361 226 143 90 263 106 46 20 247 2…
Output: 41887

Example 2:

Input: 313 -646150 730446 -252073 307188 -814118 -342393 739631 256540 -796428 595395 -189416 486901 -731251 275559 -526461 163673 -231123 832749 302374 669806 464225 34720 -346646 480371 -281139 668917 895261 286393 -949671 129323 245768 609639 670498 151729 -818204 -20227 -521489 -91716 -371046 880355 521126 -494288 -677246 -520946 -385440 776972 372255 -545103 672065 -710892 -496022 -422710 267577 695641 360659 671443 596241 -560367 -258251 -702925 -464939 -964804 888453 -600249 -863208 780565 146243 -993258 -719508 -434865 749757 761675 -404942 485247 997526 750248 -557316 -570625 -713200 -606798 489644 494952 478496 187339 -674112 -192977 416737 -522289 232381 -324531 -918869 793235 74806 575424 -350068 23154 825200 -833734 -261837 431757 773094 918547 -891378 952004 984681 -392129 488743 97…
Output: 25428

Example 3:

Input: 75 -488026 806646 167827 913146 -819664 -217649 113147 -283942 -328280 -16669 -696727 349577 88049 -41830 939863 735958 210128 -707233 -198082 68751 -421751 -424678 -996942 114638 552650 -834267 357172 970583 -541620 400156 348454 -38914 358506 314174 478985 151901 115753 973870 -540837 -751080 998606 39339 592781 -637392 -325608 -264896 -170021 -353367 431039 725533 -823323 110898 -389805 189716 232264 346128 -772882 -170148 661885 448227 840988 -534304 650128 275489 -875211 -498289 -290703 -478089 -410876 746160 -851978 477315 -244195 694957 733243
Output: 1350

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Disorder Count at Masthead - MEDIUM Coding Problem | CodeTikki