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

Hi, Codeforces!

There have already been many posts about coding speed, but my problem is a bit different (although I do struggle with speed too). I often make very basic implementation mistakes.

Before I got into competitive programming, I was developing mobile games and apps. I had written thousands of lines of code and thought implementation was my strong suit. But in practice, contests have shown me the opposite — I keep losing rating purely due to bugs in my code.

For example, in the recent Codeforces Round 1022 (Div. 2), I spent 40 minutes on the second problem, then switched to the third one. I came up with the idea almost immediately after reading the statement, but I only solved it after five wrong submissions and a lot of wasted time. In the end, I earned just about 600 out of 1500 points. In all those submissions, the logic was nearly the same — the bugs were purely in the implementation.

This isn’t the first time I’ve lost rating because of clumsy coding.

What would you recommend? How can I practice writing code more carefully? Are there any resources or problem sets where the main challenge is implementation rather than thinking?

Can speedrun of an already solved problem help?