CT61942

Last crates of Parth

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Parth inherited the studio at the wren hedges of Thimblewick along with its curious bookkeeping system for crates. 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 <= 1570; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 213 99 94 1 194 107 120 86 60 6 115 127 211 179 206 24 58 139 69 154 123 93 155 116 138 210 33 140 22 89 111 103 159 19 98 32 187 177 181 78 17 133 31 101 65 92 172 38 152 153 5 142 169 202 10 183 96 149 144 197 170 164 180 44 50 68 193 174 171 97 34 212 201 18 205 54 53 77 91 106 85 56 105 81 62 200 119 2 136 125 7 176 73 82 8 186 191 72 79 130 48 184 15 160 28 190 40 88 208 55 84 204 122 57 157 146 49 95 13 195 75 109 188 90 163 25 29 162 46 199 207 203 137 175 173 161 182 43 134 128 76 141 198 37 121 14 151 36 117 192 113 26 39 132 135 64 189 66 108 114 21 27 59 30 42 3 41 74 156 209 150 147 129 47 16 9 104 51 45 100 168 80 71 148 35 166 67 83 118 63 178 165 11 12 110 4 131 20 126 196 61 158 167 102 112 0 145 87 185 124 143 23 70 52
Output: 11983

Example 2:

Input: 1032 464634 866480 182614 -164617 -950438 698086 212240 -266624 -852462 -550490 -113417 32152 745184 -739278 -950860 -446272 -241846 656134 -425977 -282704 120785 307244 481925 -62004 -97300 288203 273910 -406192 903707 -316135 -877776 643995 -972815 671171 -465491 -295164 -300532 826591 -618931 -307466 595702 -949602 -74906 -973107 574555 -545822 103042 212188 184161 834963 -529834 -63247 82053 -396783 -313860 -157516 -378660 232727 256736 -616179 -299804 -742298 -1940 -798907 -323931 -706517 34976 47546 -690680 -127890 588788 -927174 386485 717358 845493 -646682 -17307 299574 -522880 723466 839617 197919 -318163 862247 -752774 108457 -88067 234423 -499774 -652932 817385 -251366 335635 -661124 642636 179976 681881 -292429 -232572 447641 583083 -762182 814582 346373 660289 -700804 -31640 -…
Output: 271122

Example 3:

Input: 57 9 11 28 42 45 52 38 55 8 51 1 29 18 2 24 35 6 13 49 34 26 27 3 19 37 36 48 22 46 40 43 56 32 7 20 25 17 10 15 5 50 54 4 41 21 16 47 33 23 30 44 53 31 39 0 14 12
Output: 810

Constraints:

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

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