CT49278

Gardener's Polished ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Gardener the surveyor watches over the fen lights of Will-o-Wisp's stores of ledgers. A careful computation stands between order and chaos. 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 <= 3970; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 103 268927246 938683880 366550015 441268330 611639910 980115488 697323970 362818819 75766640 326017447 722461236 963002207 499502987 479150177 202127359 864280741 537708216 843531147 1127135 923853232 212044572 667129765 83505694 752424741 987068000 319273922 798190028 296714881 528004634 209569771 364539395 166005244 110705683 582262089 768163241 765086323 826221367 234426666 509346546 291262797 27599935 136315977 880367712 969402745 383739314 879278831 126874149 380230520 844098086 144061856 126443314 58957638 367978970 934716752 545716669 623029140 675052037 556942739 326577132 274178289 879911786 880448357 778764109 961833217 83252291 137134655 438856332 809786204 638343420 962971839 302534733 667491770 408469419 919408388 705840947 98327934 810439946 535894502 545086206 200133184 7731…
Output: 2503

Example 2:

Input: 2931 578743618 265645422 35476801 611386787 656532363 834135073 827405220 669539506 172147022 920498677 460889614 717229769 337852503 13890234 808133074 767060467 551959982 508096537 149561064 808315355 831204949 782422744 953783193 415041055 164994472 428697648 656260338 810159637 418985843 932921057 204917479 674008418 555964434 995682782 409113538 566660704 68837254 4838728 230476799 212970799 413084019 514677846 270501452 855399645 170340066 390290746 608996030 704904122 787700813 132070448 399055087 789291330 485305542 668589147 589370540 887710042 518877744 784372146 5166888 371000258 306951719 709677552 333142139 430964405 288494085 153113487 232415785 11849471 114177072 882835311 664296074 837270460 567533279 76575069 466016326 537657145 152101720 532484426 94564526 467668341 21307…
Output: 2210452

Example 3:

Input: 517 12 441 46 404 210 14 273 124 409 506 156 354 339 32 300 81 391 1 272 117 461 411 348 248 382 130 295 360 145 155 429 358 378 4 50 240 30 229 252 80 152 511 138 28 33 97 136 69 218 209 204 462 20 501 139 202 262 435 114 447 35 445 397 359 285 453 148 251 498 399 490 425 185 480 405 275 374 337 303 305 10 194 88 470 187 154 323 189 221 61 31 73 99 100 54 234 383 107 25 426 325 387 116 432 484 279 448 433 141 456 2 265 467 292 427 178 304 225 159 418 150 281 64 9 486 464 188 301 259 44 366 469 321 29 71 95 311 344 243 6 151 408 454 227 70 11 129 322 26 291 3 403 168 326 314 39 266 315 103 205 288 324 157 217 57 396 270 510 282 372 497 246 398 422 481 373 165 492 316 477 417 278 47 128 79 293 439 336 146 87 45 131 306 449 91 380 208 249 434 163 18 98 296 89 93 269 41 83 140 475 167 395 237…
Output: 65294

Constraints:

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

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