CT30068

The Palemere Frugal Pairs

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Caravans arrive at the salt flats of Palemere with crates of segments, and Ravi the inventory keeper must account for every last one. 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 <= 3015; -1000000 <= a[i],k <= 1000000.

Example 1:

Input: 919 -38386 819208 -729102 -87044 -576406 -143094 -959467 -993274 887319 -206133 -808536 -26565 -894484 355144 499778 680341 880030 -95226 -28497 -262779 -757240 291058 -895835 -434872 970351 681545 -642861 126254 -471816 453874 -546084 -759449 -710119 181376 411862 -284906 -599896 660185 178924 -468974 154539 -986754 781761 56695 470998 -284333 -640118 722099 -858626 -856554 140489 545557 -329980 663483 553505 -927507 135465 671497 -199090 -42206 -946410 769682 -774723 -624260 -25586 567980 -106255 855169 -770401 928340 -844024 637960 -393926 875494 607602 -343971 609716 330590 798055 694510 -328805 -912958 404249 838646 939241 -789398 374849 304654 997679 -284183 -325553 -918124 608390 -178214 -390524 -354660 -82401 748600 -717853 -976778 335805 116280 444818 -867857 -693752 972088 505030…
Output: 202186

Example 2:

Input: 1760 1239438 425725 718040 -953469 651340 -633073 178819 -934055 551141 674477 101165 593306 -873868 415330 149078 422283 -890227 -65859 -772525 83404 -860427 -564065 -519517 728172 -885833 -988295 -480548 493786 -261568 -809702 -143835 -825777 696004 -406906 145901 -923160 946672 219920 -968271 881757 -782346 366998 -52395 923760 -182019 727647 600711 834474 -755196 -361856 -453157 806172 243186 -185964 108754 147065 661412 364544 204370 -577297 -451629 240279 808847 259808 -765328 -835711 660796 186919 -208572 194348 -73367 369424 877191 -431456 218820 -614648 -51959 891942 -651095 -246702 -550435 -970709 -769961 -365381 634031 922130 -887453 -230458 -846314 104504 -871390 675302 559889 -12377 -929593 589357 587722 -704303 384940 492313 -410395 218559 346582 731725 978793 -634286 -939275…
Output: 1448405

Example 3:

Input: 1929 1833030 9701 651975 445842 -503887 800072 -560500 -909109 -466228 -587517 -205218 -40066 303599 -923012 -903731 666164 150178 -237090 180740 437210 -44660 340163 -460243 6102 524837 128251 666590 225034 328622 447847 -3275 553038 -331784 -644401 -258090 -3430 -884230 985220 365857 562113 -299829 299934 234266 404597 900422 -272485 -311205 -331378 -903829 57615 -407596 981841 -195744 -236589 -196817 389739 -86280 -136110 -399954 164823 898588 -71054 872964 -548043 -146127 154363 -467367 -122963 -218066 -419607 294439 -647354 361793 982442 -225426 -623104 -192176 -594856 775343 -186769 -846020 362633 -466167 229692 -253908 877868 -626106 436006 -872493 -497033 -306668 221893 542605 192220 -924674 -28630 383120 -220000 837933 -837699 -478795 677490 -618137 325253 728503 -131099 -705691 9…
Output: 1853005

Constraints:

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

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