Hello Codeforces community,

I have been battling with an algorithmic problem for quite some time, and I would appreciate any insights on a sub-linear approach.

1. Inputs

There are $$$n$$$ players and $$$k$$$ gems. We maintain four arrays of length $$$k$$$: * $$$prev_i$$$: Price of $$$i$$$-th gem at the previous time step. * $$$curr_i$$$: Price of $$$i$$$-th gem at the current time step. * $$$r_i$$$: Rate of appreciation of the $$$i$$$-th gem. * $$$t_i$$$: Timestamp of the last update of $$$r_i$$$. At $$$t = 0$$$, each player chooses two gems: index $$$u$$$ (numerator) and index $$$v$$$ (denominator) with fixed quantities $$$q_u, q_v$$$.

2. Updates

At each time step $$$t \gt 0$$$, at most one of the following occurs: 1. Price Update: For a gem $$$i$$$, the value of $$$curr_i$$$ is updated. (Note: $$$prev_i$$$ takes the previous value of $$$curr_i$$$). 2. Rate Update: For a gem $$$i$$$, $$$r_i$$$ is updated to a new value and $$$t_i$$$ is set to the current time $$$t$$$.

3. Scoring System

The score of a player at time $$$t$$$ is defined by the following recurrence:

Initial Condition: $$$Score_0$$$ is given for each player.

4. Output

Find the indices of all players whose $$$Score_t$$$ is below a given threshold $$$th$$$.

Constraint: The solution must achieve a worst-case time complexity better than $$$\mathcal{O}(n)$$$ per time step.

I would deeply appreciate any help from your end!

Best, UncarvedBlock