CT41069

Aria's Scarlet weights

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Aria runs the ferry office at the caldera rim of Firewatch. Today the books show a list of weights, and the numbers must be worked out before sundown. 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 <= 2762; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 1712 65 99 593 868 77 1188 1685 738 453 663 1107 722 692 1070 1591 1307 669 875 475 393 301 644 183 1467 1110 115 52 1651 1309 1014 1166 618 1305 650 389 146 1122 1159 552 596 1703 1460 604 1164 328 706 16 17 1161 213 1532 330 1177 1241 145 654 205 704 1411 617 71 1005 700 1394 1038 1582 625 598 1346 1103 1393 624 1702 800 1409 687 797 1613 1562 531 249 717 1446 1260 68 311 116 1396 491 231 223 492 1344 1670 331 890 120 1202 518 1332 909 1387 813 1610 197 1275 1247 1696 1273 496 784 1322 1403 1658 1391 1688 1694 862 796 1390 1061 920 1534 578 1248 1548 312 135 1660 1617 979 1186 1566 1451 157 587 472 1710 1196 691 1235 276 626 948 1320 1606 345 993 302 1301 608 176 1117 463 137 1308 1513 228 1618 986 725 151 244 11 1541 1598 1557 1125 933 847 1419 781 1592 1003 1319 963 581 633 1560 707 45…
Output: 761229

Example 2:

Input: 121 65565575 527049500 609604044 519183430 604372551 527049428 629591716 766040742 666048645 422856162 623647279 427836948 611583251 944079631 729983899 590422562 104520689 679386817 311091492 768573577 205830043 628918910 470620542 543469638 197943208 75497560 754480782 860791226 309372636 846355136 785205701 822331500 749874645 298642150 334261313 475159064 680739196 775949163 517790622 66167081 243953003 388279556 147484549 116839855 535425366 237121263 63778176 919450999 255829480 7793351 773117620 876074189 194819748 475172767 91831305 352138234 562670915 326813217 336974896 376555866 95223007 524246677 89115270 664819319 783746711 589423624 499146367 485732802 586803654 102812623 108908726 274301406 107985344 491438256 408909220 914107118 926311999 320532601 261154438 286556560 18833…
Output: 3667

Example 3:

Input: 1370 219 825 1288 1076 30 611 1020 546 1063 205 543 1082 155 167 1073 908 714 152 29 597 1108 578 598 1220 1274 1311 128 1309 104 907 736 69 1167 181 55 610 971 32 595 553 1217 353 227 699 391 1161 1169 720 909 26 846 1144 960 760 906 17 1080 147 656 861 1326 969 374 767 931 46 535 266 511 1150 1185 137 180 1325 7 800 777 1190 1181 523 190 1243 1135 1193 593 268 721 134 663 348 1175 1199 1364 935 1021 1270 1291 729 1369 1339 1049 1170 877 253 365 801 279 423 1240 999 210 915 942 400 378 1206 588 1139 728 140 882 807 526 115 380 165 1078 1284 1314 1329 1174 791 894 1300 474 633 1006 1079 1250 530 457 733 470 537 705 189 376 274 81 1351 372 295 619 347 902 990 1330 847 239 144 1333 574 0 893 837 241 298 131 1262 1057 67 766 982 1317 164 1347 1228 555 1236 517 864 1296 125 579 1071 1187 35 10…
Output: 476343

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Aria's Scarlet weights - MEDIUM Coding Problem | CodeTikki