CT31896

The Frugal Pairs Beneath Serpentis

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Ivan found an old ledger of stretches in the salt store attic at the jade shrine of Serpentis. The margin notes pose a precise question. Task: Print the number of index pairs (i,j), i<j, with a[i]+a[j] <= k. Input format: First line: n and k. Second line: n integers. Output format: Print the pair count (fits 64-bit). Constraints: 2 <= n <= 1976; -1000000 <= a[i],k <= 1000000000.

Example 1:

Input: 1900 1198037402 309419563 794725547 397339407 409632411 135622296 66949509 978284047 793919906 685521102 912807697 492318158 267843024 399358715 462063446 994316774 66743294 728187587 211958480 812665744 674811150 97329859 262018883 416437697 460482614 516397060 320470974 980995832 135072266 292138891 736767466 260614013 5816053 777688831 389333951 611441562 891633387 765587645 777219102 919794612 25533975 554320385 675171655 35091449 373324458 804895333 575505561 333105155 203473179 851895353 516950237 925748304 264046577 530800281 387140616 302764256 278628491 800655418 403775709 599990124 770039101 705628289 4913756 901580384 715985218 746317844 34640458 30669437 162188752 749392145 906389212 219834900 82433305 168043667 697292400 671556690 766587105 544299555 306669689 300304452 742075…
Output: 1163481

Example 2:

Input: 349 1702877792 497089302 518054170 875844272 240347932 260011058 564634455 627659533 983637118 360058484 896232778 674007796 219337630 811060606 295065481 171924705 756379377 277541570 114036642 379699765 417869216 217944096 408902711 937233926 471690612 675052751 804490998 222193182 6239829 659054262 635042920 37220528 688130500 305968319 923380038 585194509 714026162 637808128 143787335 136465173 755559130 761178542 771285998 208217775 341283326 648528840 236548071 669256434 241225848 174845061 609248237 4678778 132214035 377542755 725869360 986340371 854236763 671401891 301582469 961584321 664810855 227559865 36854031 823128175 461835089 252777578 817792932 190722421 449668791 372450548 705045884 203260082 88459043 123145648 720636308 468587942 242492976 278310653 621319585 375630620 75…
Output: 59121

Example 3:

Input: 837 1368285038 261833181 592325439 110090199 706073644 225129483 12506820 815522304 375038962 541385910 25807637 711998398 342240166 547017276 982070236 724666110 189094890 133659438 932278012 301123719 77005000 100341443 427062859 727453549 575249157 786765139 281445890 620044410 767051581 583145790 92562394 760132590 348864267 514127104 44634545 268277658 711883826 57414836 420703300 4771620 991251971 362943831 8948966 339613325 39681566 489850277 257796618 273502020 754724642 554599029 345339960 969713139 205883444 847762681 244356175 754040492 345276833 749983775 388350023 924141681 255659760 98749048 617078357 29997047 298655544 721869090 963106149 907729528 221768054 601623062 429478886 249001553 21729781 639459122 38181061 499527571 53819041 519071719 188634892 503041392 619443281 8…
Output: 277432

Constraints:

2 <= n <= 1976; -1000000 <= a[i],k <= 1000000000.

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