CT42777

The Frugal Pairs of the Verdant segments

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the lakeside town of Mirrormere opens only for a perfect tally of segments. Ishaan means to find out. 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 <= 2145; 1 <= a[i],k <= 1000.

Example 1:

Input: 1676 320 263 362 874 689 625 56 234 555 905 665 370 843 166 773 104 756 202 449 283 360 8 523 193 918 272 919 366 208 994 197 717 407 453 874 847 373 413 928 486 791 463 424 836 727 518 772 737 117 72 33 238 50 943 360 996 207 127 663 825 699 802 80 55 241 276 560 843 979 457 865 508 782 542 351 896 220 863 720 561 842 69 188 491 822 589 446 68 180 526 870 255 74 458 521 501 165 373 853 540 613 547 220 922 909 567 704 832 703 55 151 380 656 64 568 302 184 336 352 442 565 223 103 637 696 421 727 743 93 213 597 254 865 727 978 776 285 886 843 159 567 138 530 673 935 606 502 604 58 293 393 639 860 988 6 380 564 381 981 439 464 841 544 996 86 764 414 523 673 496 89 204 220 175 501 237 218 419 268 243 911 774 586 164 548 502 113 868 264 859 220 490 422 227 887 752 576 945 135 310 727 188 685 23…
Output: 69216

Example 2:

Input: 1501 1695 548 453 16 892 987 141 631 422 681 707 585 269 496 30 234 350 341 750 164 804 92 772 58 836 363 48 150 250 681 688 477 611 798 354 244 468 425 821 703 172 126 807 931 241 415 173 438 502 962 181 399 165 138 266 887 789 111 437 503 287 510 977 152 646 273 992 719 687 906 436 650 358 812 178 314 782 718 535 322 70 940 452 404 192 775 629 462 370 213 806 490 588 257 770 949 158 935 263 482 610 344 669 874 679 441 96 789 76 980 636 855 343 964 341 455 814 826 519 479 88 217 705 304 373 487 413 927 424 610 77 397 31 390 644 320 606 177 322 467 754 640 557 983 869 34 214 90 783 803 971 465 366 527 463 332 423 260 834 188 681 969 389 290 771 790 911 962 395 326 922 391 103 892 183 371 930 395 810 263 261 720 152 855 378 304 955 784 991 901 73 556 912 663 434 54 894 732 301 830 469 310 2…
Output: 1071811

Example 3:

Input: 561 110 125 328 417 685 382 299 86 325 606 407 152 465 593 162 933 873 150 599 739 722 537 852 974 859 40 776 266 180 788 429 313 232 196 665 677 410 602 466 782 776 208 933 4 134 361 409 14 552 116 158 431 211 955 115 812 103 838 232 209 142 598 502 601 393 720 824 952 481 722 911 87 138 764 31 88 193 499 898 840 536 552 155 984 738 604 685 500 392 487 946 623 517 420 479 408 386 597 123 248 96 856 789 574 763 816 484 700 835 403 143 783 738 279 590 941 980 225 335 600 158 772 896 649 75 190 409 627 658 15 153 151 488 743 421 393 499 978 410 558 897 795 198 766 533 667 180 476 576 372 408 30 4 689 83 91 68 524 287 999 620 142 911 799 925 786 890 251 334 900 595 495 420 73 529 251 657 81 704 908 606 635 361 314 935 179 226 705 493 193 30 5 79 655 269 885 159 348 680 743 467 828 692 544 217…
Output: 830

Constraints:

2 <= n <= 2145; 1 <= a[i],k <= 1000.

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