CT62478

Ivan's registers Reckoning

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Ivan inherited the archive at the forest village of Briarthorn along with its curious bookkeeping system for registers. Time to make sense of it. 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 <= 3457; 0 <= a[i],x <= 1000000.

Example 1:

Input: 341 279 25 99 48 3 65 331 88 67 258 23 26 327 182 268 131 164 172 216 70 77 212 180 71 225 43 330 310 94 152 98 101 253 229 139 211 102 37 334 111 200 213 56 301 256 242 248 179 204 233 29 276 311 133 316 100 42 74 4 299 203 78 243 155 59 1 14 90 338 34 7 57 188 244 163 198 51 20 329 137 228 205 157 251 47 169 283 5 340 245 18 86 144 123 127 190 289 45 38 297 267 84 230 118 92 284 224 159 246 36 154 185 143 226 222 52 328 80 287 8 322 148 120 255 113 231 184 263 44 181 339 320 124 175 69 79 107 247 60 16 302 168 49 318 150 294 0 40 240 325 158 208 147 22 215 306 304 259 162 295 58 270 160 280 64 10 241 68 50 202 273 121 165 300 223 196 149 135 63 315 265 21 153 19 46 82 145 207 87 288 313 156 298 116 201 126 66 166 132 272 324 238 239 281 286 321 277 97 308 197 187 249 309 332 142 206 32 2…
Output: 28269

Example 2:

Input: 2990 674761 240297 969359 923637 612148 172860 92699 177805 810937 911375 303532 948535 854414 177298 228324 970297 457303 931534 541731 130933 551917 391294 799385 931871 632006 951059 915993 935111 581062 520467 764406 435523 626673 725489 905498 331538 697120 230797 617263 730382 710637 676417 829884 992716 696986 88371 727474 592112 979201 294142 88499 908267 320348 591222 684251 575081 543959 670307 236084 479647 155691 234941 720476 820941 682184 59901 631485 267263 973058 959416 399751 775733 134641 839539 50919 983867 760922 183285 383776 80677 251795 898953 104697 625918 423410 374439 451313 687264 781722 649925 235947 978357 121385 72308 635701 665978 980673 814561 559004 731473 675620 36160 176548 854190 300926 209773 860519 802516 752508 318947 158380 595999 377616 265045 23402…
Output: 2232999

Example 3:

Input: 2206 386536 12675 140847 650618 686073 373081 669634 419889 75522 864987 657481 337567 502146 2223 17744 917738 188861 261262 898963 209528 493197 436562 459540 35112 690602 892246 833045 758994 917023 260863 511676 86991 862225 137301 225397 516026 959423 185180 100865 611386 60761 727939 720865 635650 486339 855084 969771 571967 105921 991693 842678 618612 301406 767437 871751 759014 924637 742536 360999 670894 647635 713701 226894 268629 273795 724057 708839 872267 261910 302694 10729 687079 760996 757027 737388 489791 203862 401877 991170 714824 418106 92444 377558 938570 554010 718848 499012 307567 535380 591972 223397 206708 223862 850664 423438 880831 143438 928439 851985 527619 471166 289571 287125 929309 547775 891473 731451 251022 200366 668306 310422 852011 19060 731390 11166 61…
Output: 1209506

Constraints:

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

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