fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Codechef {
  6.     public static void main(String[] args) throws java.lang.Exception {
  7.         Scanner sc = new Scanner(System.in);
  8.  
  9.         if (!sc.hasNextInt()) return;
  10.         int n = sc.nextInt();
  11.         int k1 = sc.nextInt();
  12.         int k2 = sc.nextInt();
  13.  
  14.         long[] arr = new long[n];
  15.         for (int i = 0; i < n; i++) {
  16.             arr[i] = sc.nextLong();
  17.         }
  18.  
  19.         // --- PRECALCULATION: Suffix Sum of Pairs for k2 ---
  20.         // s[k] = number of valid pairs (k, l) such that k < l and arr[k]+arr[l] > k2
  21.         long[] s = new long[n];
  22.         long[] suffix = new long[n + 1];
  23.  
  24.         for (int k = n - 2; k >= 0; k--) {
  25.             int start = k + 1;
  26.             int end = n - 1;
  27.             int firstL = -1;
  28.             long target = (long)k2 - arr[k];
  29.  
  30.             // Binary search for smallest l > k
  31.             while (start <= end) {
  32.                 int mid = start + (end - start) / 2;
  33.                 if (arr[mid] > target) {
  34.                     firstL = mid;
  35.                     end = mid - 1;
  36.                 } else {
  37.                     start = mid + 1;
  38.                 }
  39.             }
  40.  
  41.             if (firstL != -1) {
  42.                 s[k] = (n - firstL); 
  43.             }
  44.             // suffix[k] stores total pairs available in range [k...n-1]
  45.             suffix[k] = s[k] + suffix[k + 1];
  46.         }
  47.  
  48.         // --- MAIN LOOP: Iterate j to find pairs (i, j) ---
  49.         long count = 0;
  50.         for (int j = 1; j < n - 2; j++) {
  51.             int start = 0;
  52.             int end = j - 1;
  53.             int firstI = -1;
  54.             long target = (long)k1 - arr[j];
  55.  
  56.             // Binary search for smallest i < j
  57.             while (start <= end) {
  58.                 int mid = start + (end - start) / 2; // Fixed mid calculation
  59.                 if (arr[mid] > target) {
  60.                     firstI = mid;
  61.                     end = mid - 1;
  62.                 } else {
  63.                     start = mid + 1;
  64.                 }
  65.             }
  66.  
  67.             if (firstI != -1) {
  68.                 long c1 = (j - firstI);
  69.                 // All pairs for k2 must start at index k >= j + 1
  70.                 long c2 = suffix[j + 1];
  71.                 count += c1 * c2;
  72.             }
  73.         }
  74.  
  75.         System.out.println(count);
  76.     }
  77. }
Success #stdin #stdout 0.15s 56548KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8le1m3
language:
Java (HotSpot 12)
created:
74 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!