CT63365

Archivist Counts the vials

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Archivist runs the exchange at the marble forum of Argentium. Today the books show a list of vials, 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 <= 2087; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 1053 100232459 851174292 404452146 988838416 527044104 679462688 22959510 969805019 493508272 113016549 71583677 439829887 706034950 135494886 883576615 160910362 145619189 80343667 302510421 78887367 613699803 242666816 933544955 947914770 483919827 580833358 911515867 559956108 840398956 888773838 872607903 254381964 210425458 677906077 202731082 789360241 781077230 70587342 858958912 641880555 431075351 262575498 876624376 990249541 766047839 286743601 706232335 316723941 183265458 46109113 859978946 650486361 196321386 347037597 187696015 941935396 250906849 130706057 606590775 655438299 134339003 646166207 788114522 719002378 355153802 137056397 373576986 466883248 857835325 322920798 400626146 97150896 381686248 664089571 61081841 297552624 626237511 55385547 681709635 998687094 3984…
Output: 274822

Example 2:

Input: 600 752653595 737413946 86419393 853097050 880291331 64321086 780347830 935024279 481952539 277605007 77200251 373231317 995918459 188497117 640998968 142148706 86554344 590124938 652030273 375515553 70960785 184101167 603106882 326423528 251508215 388311328 662690362 805130975 785410492 332669893 94837305 173789333 125917571 612175686 671049889 66057380 661416556 721817839 170746306 816414089 195038840 414653403 41647679 505432514 442780895 742003400 301595210 808615250 325191943 69749866 963720608 610553047 581648494 885295842 608789215 926353917 772744369 169250216 268537833 518904375 711296704 126678356 845554508 248590334 975536275 631297144 54066168 200213646 408973317 980543936 38147628 570000432 994167032 338850174 938353773 677077218 972068435 243260453 416965709 631565933 4785167…
Output: 89929

Example 3:

Input: 1982 379618745 979122438 186973297 875197039 121722123 249118205 944254547 969857996 453918825 120314128 8977754 154857621 393255536 308740992 460649986 591707255 112824443 288273127 991884350 35643630 485687751 899625394 884836870 849343489 868393055 752689970 429390818 120691565 939385421 804220417 62365240 570763727 156531599 38904116 292496988 700619742 78735586 972513219 418982596 613301754 503063093 205012 899454448 455856215 310465897 93275775 954797605 20475137 985972664 867708016 150105650 577082443 203286130 78321684 294217771 254973625 419835519 369097511 215765430 996065043 415397968 719266645 255801297 51123583 224097862 339041522 292246654 35992043 506879087 614999715 105914332 245921976 98866767 325437665 866772714 189504531 219373776 917348270 290863819 993614072 334163252 …
Output: 970816

Constraints:

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

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