CT33871

The Frugal Pairs Beneath Selene

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

The council of the moonlit lagoon of Selene pays by the answer, and Leon intends to earn it. First: the full register of segments. 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 <= 3758; 1 <= a[i],k <= 1000000.

Example 1:

Input: 1800 1059138 584836 198596 797827 401691 755492 929479 371765 486234 542171 68581 281024 598261 918484 459201 943835 232865 936654 508433 114061 31326 547452 761577 718391 146140 362833 144217 582256 839007 17835 172320 122774 65935 10192 745869 391957 615513 501861 960448 726503 766482 993449 748811 642861 613202 282905 856104 646370 963382 613488 833977 711756 705684 485451 918914 240281 182966 472180 217055 744277 135287 787892 802858 391523 452439 80676 667233 575629 281135 65460 4302 120921 295886 95707 804063 166371 985306 213713 871252 342168 862433 346240 894061 348434 641121 353019 159144 859075 750837 415861 822720 272303 452149 269582 190070 42542 9371 520933 131409 73117 860016 550875 992533 967123 214321 267663 448117 797312 355129 319286 865190 179255 972958 229132 659001 752…
Output: 908731

Example 2:

Input: 1113 1335722 510076 657537 151051 404445 237931 172289 99470 117843 904131 967814 950071 325415 86534 622808 563528 202624 909549 456485 977338 401338 977651 444155 967792 392665 742956 472612 921569 896971 945498 38552 848352 632455 215935 114542 563319 88690 509018 500669 520203 936682 23054 464170 890586 260029 875521 229386 510937 326219 132913 666522 134447 739310 122254 179876 279600 529629 487978 908652 592019 60318 341527 130 689147 739012 112882 637889 898657 870888 430678 235882 196067 357149 302067 314950 316008 905201 973442 935228 397823 278668 551431 527446 627440 339460 815326 554175 125472 896276 482554 157694 148967 411003 468355 981948 58490 889897 539183 530398 817497 75464 439049 284622 102247 419554 313359 561622 569985 70280 743366 209591 790481 707028 606424 924097 2…
Output: 489431

Example 3:

Input: 730 1900616 589554 583957 142372 175300 206712 439156 257067 708154 423602 360164 358035 534883 752873 847728 762326 40014 444184 663438 916929 711249 869402 760468 730060 243439 889754 436438 256872 568999 707933 141625 687498 602311 107397 547448 658460 425226 185982 907138 264312 222177 606237 38376 357684 671721 900597 977660 502703 915235 960763 855654 292728 600999 455543 913410 683694 509056 149091 622169 502732 880654 799092 635297 775412 635129 237953 783446 758941 409623 107453 550297 624104 211787 927576 632021 366509 671708 71105 970521 761590 95785 22710 977840 491487 935347 865493 173985 483142 291865 880623 130443 195886 310513 966956 973529 65851 727490 522552 384416 523737 906709 638677 484564 773220 174250 575358 969381 47543 744958 115634 146030 318573 781425 371144 2794…
Output: 264906

Constraints:

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

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