CT34286

Ysolde's segments Reckoning

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Ysolde the chronicler watches over the shipyard of Keelwind's stores of segments. A careful computation stands between order and chaos. 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 <= 3667; 1 <= a[i],k <= 1000000.

Example 1:

Input: 2457 1942936 656113 805263 773010 225020 747969 540305 626516 363602 136145 670967 23767 703379 352241 293630 595332 791315 174342 709503 94228 615045 631585 346135 78006 631175 802542 807948 355643 327470 968407 112341 64551 11704 785102 207670 342911 16030 679164 915242 944107 859301 843557 100846 292508 58049 554211 617542 152806 591194 229752 179292 166055 273768 748463 528624 708308 863169 666056 32818 706839 332645 895784 528258 799313 518483 621476 343224 721839 516257 611286 770992 817093 621154 171162 160980 885911 957395 80793 417461 678299 88679 552082 729202 713518 524881 347973 180210 473314 5471 448491 351673 970700 276230 461137 570886 720196 528154 500685 627756 120901 395449 503829 679490 759968 517068 486827 494569 8857 908639 987850 64186 947482 121940 74101 835938 33764…
Output: 3013155

Example 2:

Input: 3256 243242 717186 665846 383022 315570 5249 552799 791885 513545 822212 929071 914694 95346 779757 695726 277995 561412 355606 338131 598447 124565 966239 503727 853002 476864 476391 915420 629479 936734 159259 280959 106675 435160 82952 449644 229380 505730 239158 855257 756127 41112 553532 192615 485658 7398 663208 359990 165932 443113 108114 596050 35312 371769 846203 532518 31793 737194 115073 649800 991253 342687 932670 938163 739435 748395 679485 16377 6737 144324 23993 880122 930713 54545 692610 976231 746007 848148 458061 924238 871171 296709 142926 993781 599056 221693 677057 300707 410316 758069 430308 585805 254952 752173 593158 610363 573545 431022 391462 692698 183943 713346 803231 791998 968519 971 121706 154242 340287 605585 756703 937732 371991 161500 117560 696206 918693 …
Output: 163602

Example 3:

Input: 66 293507 516629 413172 355218 348728 528241 411195 466540 46558 306627 297912 755703 814775 451365 487636 297663 763593 855085 983035 213896 63910 468010 17026 833899 131354 751443 745837 358818 111178 777674 129204 514701 798647 292224 996124 851407 50150 692494 987189 542090 374407 170005 974941 160500 884800 73211 516757 844222 706160 724330 39098 338476 206021 841824 719926 378182 370418 725277 552797 30851 179072 778616 598465 2082 329419 403479 909957
Output: 100

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Ysolde's segments Reckoning - MEDIUM Coding Problem | CodeTikki