HCCoder's blog

Need help solving problem
By HCCoder, history, 10 months ago, translation, In English

You are given an array a of length N and an integer k. Your task is to find the number of index pairs (i, j) that satisfy the following conditions:

i < j

k * a[j] * a[i] > max(a[i], a[i+1], ..., a[j])

Input:

N — the length of the array (1 ≤ N ≤ 2 * 10^5) k — an integer (1 ≤ k ≤ 10^4) a[i] ≤ 1e9

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
7 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I can think of an idea derived from 2 famous algo

1) quick sort 2) divide and conquer

You find the max element that will act as the pivot than Partition into left and right Let x = value at pivot

From the left and right side find the smallest side

Let's assume left is smallest

So iterate through each element of left and than using fenwick find count of Value greater than ceil( x/ k * left[i])

Now do and divide

Now that we have 2 partition do and divide and conquer and solve for left and right

→ Reply