CT54456

Smith Counts the windows

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the ivy courts of Vineward, someone must chart the migration season. This year the task falls to Smith, armed only with the windows register. 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 <= 3707; 0 <= a[i],k <= 1000000.

Example 1:

Input: 3583 1259968 774754 496121 536366 250416 218299 587418 400094 932121 172651 917415 64062 940480 330967 981421 181206 969077 796327 825363 23307 626624 897918 375551 75809 572510 852610 529284 331879 244057 892761 781842 53698 238206 975530 840954 303191 744886 460564 177274 381635 766990 674002 110602 495820 423324 202661 709382 8349 518839 799758 267067 438936 369767 424804 74179 285965 836077 389198 115456 739706 442908 343061 289121 432171 367035 304095 954439 986704 564379 157261 728091 875867 115211 897909 429604 316830 912862 481926 212802 707031 757667 483184 514941 427513 456721 725807 221306 126203 901626 228716 441056 375103 625048 599684 418053 659075 796278 354234 416102 24684 805515 961512 459991 231437 686300 363769 108688 628183 142795 250012 633781 95863 460410 864961 63832…
Output: 4688388

Example 2:

Input: 351 1620273 296885 763647 247049 121844 399352 25245 398340 354926 489805 737258 944911 843225 849791 361061 432040 165743 432379 532294 717416 789652 323031 896523 955972 648107 815600 215534 41959 566412 936212 365657 989596 410805 136890 803830 695740 149335 780401 431539 796972 70552 93396 217635 530129 537099 130712 955353 449803 783904 46768 996731 390348 365602 942393 664081 181097 537404 796448 37645 740360 311233 315221 891397 760337 957284 661911 906434 411492 886421 232382 443426 747429 108768 830483 464668 901175 266896 998853 738523 324320 846283 895385 67525 993175 815210 669875 451429 983206 735470 133369 51989 319301 984003 542786 29976 73749 950849 822858 429812 68073 102467 398115 989677 357690 80656 504392 215079 673635 48787 785190 626913 570416 138434 759392 64363 1844…
Output: 56690

Example 3:

Input: 2902 1707858 600264 135767 238359 539340 954769 144256 916361 685904 141716 641894 468423 828746 706061 984344 758514 371548 209155 260146 240421 62387 382212 958715 443194 152618 282363 572230 795559 145894 620053 391642 575298 472875 300582 85970 315155 853328 100763 328456 303875 539613 959257 530320 255178 917218 835506 146884 949398 646539 494712 484171 807898 538608 648671 190880 728725 991163 47703 512536 18153 16487 925706 3565 759453 480240 116579 85178 712913 812082 764633 862720 896674 658249 700380 685075 992801 984514 449420 337483 776264 954902 360455 135112 801115 939850 707936 98453 966879 934735 107989 2466 379625 993509 144668 519960 712762 631586 487492 995016 382112 166852 915384 646856 358684 858388 738099 350387 367190 528106 405211 234196 261241 979217 475711 73610 8…
Output: 4025897

Constraints:

2 <= n <= 3707; 0 <= a[i],k <= 1000000.

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