Hello, CF community, I found this 1700*-ish problem, can somebody help?

Given $$$n$$$, $$$d$$$ positive integers, and the array $$$a$$$ with length $$$n$$$

for each $$$i$$$ s. t $$$1 \leq i \leq n$$$

Find the maximum j s. t $$$\vert{a_i - a_j}\vert \leq d$$$

**Input format:**

Integers n,d: $$$1 \leq n \leq 1e5, 1 \leq d \leq 1e9$$$

In the next line given $$$n$$$ integers representing $$$a_1$$$, $$$a_2$$$, ..., $$$a_{n-1}$$$, $$$a_n$$$

**Output format:**

In single line for each $$$1 \leq i \leq n$$$ output the corresponding $$$j$$$

if there is no corresponding $$$j$$$ output -1

I'd appreciate a solution without any kind of advanced data structure(___Trees, ___Arrays, etc)

Thanks for any help

For all a

_{i}, Find max j where a_{j}is (> a_{i}and <= a_{i}+ d) and( < a_{i}and >= a_{i}— d ).You can use binary search for this

You know you can't run binary search on a random array with no logic? and if you know a way please provide me code and I'll try to understand it, thx

store the array with index then sort, then use binary search to find the range. then max j in that range using segment tree

As I mentioned earlier in the blog, I don't know any advanced data structures including segment trees, and I don't believe in knowing one until I'm not around 1900 and I believe every question can be solved without them(and it worked out better than you're strategy, knowing one)

So any other solution without a segment tree be helpful thx again

just replace the segment tree with two pointers (since ranges will be increasing as you move left to right) and maintain a set of values. From that set, you can get the maximum $$$j$$$. unless sets are too advanced for you?

Not knowing is fine, but refusing to know until reaching some level is stupid. It's reasonable to not want to spend time learning it, but refusing to ponder specific solutions paths will only hinder you from having more creative and exploratory thought process. Instead try to find any solution path while considering what things that seem reasonably possible you aren't sure of, then ask yourself how to do or how to simplify those parts of it (or eventually consider it's wrong approach).

Also segment tree is not advanced in itself, it is basically just writing out all possibilities of binary search.

lopital24's idea with two pointers is what I would do tho.

About that, It's basically for INOR. Hard to explain, but just wanna tell you that I've wanted to learn it maybe 10 times? but the INOI thing stopped me, so yep, I'll wait for that time

Well you can see right here, instead of disregarding segtree, if you reduced to "i need max under range with these conditions" and continued thinking various possibilities, you would've got to the two pointer idea. But instead you dismissed lauhemahfus's approach completely.

My point is not you need to learn, but considering applying or using parts of ideas even outside the scope of whatever contest you're working towards can be a stepping stone towards a simpler solution. The goal is to figure out the fundamental steps to get to a solution, not just going through and trying to modify whole solution of different problems you've seen.

I see, thanks for the advice and your time

(I'll actually listen)

yeah maybe lately I've been focusing on

solvingthe problems instead ofthinking/enjoyingthem which caused this. Now I don't go deep into a solution, if it has a unfigured out part, I'll Just skip to the next ideaThanks, it was a needed realization

We can scan through given array from right to left, supporting set of indices, answer for which has not been found yet.

Let's suppose we are now in index $$$j$$$ and we want to find all $$$i$$$ s.t. $$$j$$$ is the answer for $$$i$$$. These $$$i$$$'s values are in range $$$[v[j] - d, v[j] + d]$$$, so just finding, processing and deleting all such $$$i$$$s suffices. As I understood, the answer for particular $$$i$$$ can never be $$$-1$$$, because $$$a[i] - a[i] = 0$$$.