CT33797

The Frugal Pairs of the Dusky segments

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Morning light hits the cedar groves of Balmcrest as Quartermaster unrolls the day's manifest of segments. The tally will decide the next shipment. 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 <= 3532; 1 <= a[i],k <= 1000000.

Example 1:

Input: 3117 1773404 617227 5156 447966 541863 232878 254957 831708 579137 323186 176346 1108 117919 693286 559568 171580 679188 747838 896535 868626 933341 31375 969310 896942 958089 898679 881234 439913 551924 595233 568629 78427 227437 674047 395858 758843 194730 436436 768966 549426 258616 419273 779359 60931 426510 954657 11503 983492 678792 569233 426199 519581 782481 100629 891547 530716 942170 937755 475153 129977 875751 872629 702159 240083 976660 333072 855674 439798 824017 358165 993852 739381 683300 928737 57508 988699 693503 637463 854751 412105 593231 708124 566107 71865 232765 362612 755836 660354 704051 318111 260127 496275 104290 443972 572650 726328 172477 523111 160789 319351 720965 529520 818660 386933 963001 841934 850477 693884 623281 309294 133512 892762 519944 449671 184873…
Output: 4743363

Example 2:

Input: 2873 867998 174477 450424 871477 879959 466892 158526 620622 634908 63435 991041 345288 671810 62197 356500 668455 988454 93110 491128 17249 469679 956385 43742 610449 227596 241894 258150 642270 117619 682046 175971 437997 360658 40382 52711 139932 88327 935025 823808 82143 170625 564398 444499 36951 803722 523358 260219 260466 579627 917496 794720 103113 871223 793106 829258 822465 883273 71866 297408 114858 173135 707064 598706 902097 315500 483652 410131 587642 962814 892993 557957 309973 930650 178195 257027 900103 372813 28339 136468 777179 939007 700100 938756 338890 179288 12253 38856 147609 690965 780329 927104 158845 330229 832860 782827 300717 929058 385077 771453 423121 904346 813797 33177 831929 357341 860870 487972 822901 670300 156785 471127 529568 924567 695269 425378 43858…
Output: 1506429

Example 3:

Input: 739 1527126 940431 502306 780060 30856 394075 748396 48362 602427 882222 688115 303172 192251 673385 363298 654959 625101 350739 377756 454418 292276 490589 579860 703787 1798 938567 659518 227171 151913 659388 215138 554861 531448 2634 977158 44676 556915 156329 55513 141536 701454 780379 283072 978155 685367 15356 842512 861970 917117 371181 442426 96312 539718 453250 235721 61737 971879 803896 222716 55023 52783 453143 268650 783168 985956 479857 427637 434630 463758 207444 475240 875758 478438 28850 692743 396949 365284 658400 141172 48484 827997 868342 578689 497222 569278 444005 179618 269241 10197 586875 688421 396534 36884 907165 535653 123056 463546 717041 882839 526548 695166 607884 194253 560984 198473 259202 311255 322946 255920 60227 783047 698185 497360 706815 851184 48453 52…
Output: 246474

Constraints:

2 <= n <= 3532; 1 <= a[i],k <= 1000000.

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