You can solve each row independently of each other. Using window sums, you can count the number of A or B in any contiguous section of $$$K$$$ cells, and thus detect whether any player has an opposing player in front of them.

Time complexity: $$$O(NM)$$$

The key observation is that you can think of the students as a queue standing from $$$1$$$ to $$$M$$$. The students that answer the $$$i$$$-th question are always the first $$$B_i$$$ students in front of the queue, then they move to the back of the queue in the same order that they were in before. We could prove this by induction:

• To avoid having to consider tie-breaking, we let each student $$$j$$$ start with a score of $$$j \cdot \varepsilon$$$, where $$$\varepsilon$$$ is a really small fraction.
• Let $$$P(i)$$$ represent the predicate/statement: Before answering question $$$i$$$, the students in the queue are strictly sorted by score and the difference between the scores of the first and last student in the queue is less than $$$A_i$$$.
• $$$P(1)$$$ is trivially true. Let's prove that $$$P(i)$$$ implies $$$P(i+1)$$$ for all $$$1 \le i \lt N$$$, which would prove that $$$P(i)$$$ is true for all $$$1 \le i \le N$$$.
• Let $$$S_1 \lt ... \lt S_M$$$ represent the scores of the students before answering question $$$i$$$, from front to back.
• Answering the question and moving the students to the back of the queue preserves the strictly sorted order, since $$$S_M - S_1 \lt A_i \Rightarrow S_M \lt S_1 + A_i$$$.
• Now the score of the new-first student is $$$S_{B_i + 1}$$$ and the new-last student is $$$S_{B_i} + A_i$$$. Since $$$S_{B_i} \lt S_{B_i + 1}$$$, the new difference is $$$S_{B_i} + A_i - S_{B_i + 1} \lt A_i \leq A_{i+1}$$$, therefore $$$P(i) \Rightarrow P(i+1)$$$ is proven.

This gives an $$$O(NM)$$$ solution, but we could optimize it by realizing that since scores are always added to up to two contiguous segments of students, we could use a finite difference array (to add $$$x$$$ to a contiguous segment $$$[l, r]$$$ of the original array, we add $$$x$$$ to $$$D_l$$$ and subtract $$$x$$$ from $$$D_{r+1}$$$) and restore the answer by its prefix sum.

Time complexity: $$$O(N + M)$$$

The tournament is modelable as a perfect binary tree, where the first round are the leaves of the tree, the next round are their parents, and so on. Let each node of the tree contain both the maximum number student and the sum of the "underwhelmingness" of the matches in its subtree. To shift the missing student means updating two leaves of the tree and their ancestors, which takes $$$O(\log N)$$$ each time.

The perfect binary tree can be modeled as an array indexed from $$$1$$$ to $$$2N - 1$$$; the leaves are nodes $$$N$$$ to $$$2N-1$$$, and each parent node $$$i$$$ has children $$$2i$$$ and $$$2i + 1$$$. If you are familiar with a data structure called a segment tree, it should form this perfect binary tree when $$$N$$$ is a power of $$$2$$$, and the answer can then be obtained from its root.

Time complexity: $$$O(N \log N)$$$

First, reorder the candidates by the given ranking, indeed, you may want to do this even before trying to solve this problem, as it makes things easier to visualize. For example, the sample input becomes

3 4 4
3 4 4
1 4 4
4 4 2
2 4 2
1 4 1
4 3 4
2 3 3
4 1 4
2 1 2
1 1 2

We'll refer to this reordered matrix by $$$R_{i,j}$$$.

It can be seen that any possible first factor must have non-increasing scores when looking at the ordered candidates. Once the first factor $$$j$$$ is chosen, it essentially splits the list of candidates into several contiguous sublists where $$$R_{i,j}$$$ are all equal. A factor becomes a possibility for being the next one if they are non-increasing in each sublist.

To update the possible next factors efficiently, consider a "bad row" $$$i$$$ for each factor $$$j$$$ to be where $$$R_{i, j} \lt R_{i+1, j}$$$. The candidates for first factors are those with no bad rows, and picking a factor $$$j$$$ will nullify bad rows $$$i$$$ for other factors where $$$R_{i, j} \gt R_{i+1, j}$$$. Note that each row should only be considered for nullification at most once. This can be efficiently done by storing a count of bad rows for each factor, and a priority queue or ordered set for the factors with no bad rows (to ensure we always pick the minimum possible factor each time).

Time complexity: $$$O(K (N + \log K))$$$

Consider a function $$$f(l, k)$$$ to return the minimum position of a student blamed at least $$$k$$$ times, given that the leftmost interview is at index $$$l$$$, or $$$\infty$$$ if there is no such student. Note that this can answer queries simply by comparing the returned value with the given $$$r$$$.

We solve the queries offline by considering how to transition from being able to answer $$$f(l+1, *)$$$ to $$$f(l, *)$$$. Let's have an array $$$F_k$$$ that stores the answers for $$$f(*, k)$$$ where $$$k \leq X$$$, where $$$X$$$ is some threshold value we decide later. To transition from $$$f(l+1, *)$$$ to $$$f(l, *)$$$, we use an array of growable arrays, where growable array $$$i$$$ is the list of blames for student $$$i$$$, in decreasing order. We can easily add the blame for student $$$A_l$$$, then look at up to last $$$X$$$ items of that list to update $$$F_k$$$.

This allows us to answer $$$f(l, k)$$$ for $$$k \leq X$$$. To answer for $$$k \gt X$$$, we store any student that exceeds $$$X$$$ blames into another growable array and call them heavy students. We can then answer those queries by searching through the heavy students, as they are the only students that might have at least $$$k$$$ blames. There can only be up to $$$N / X$$$ heavy students.

Therefore, we can answer all queries in time $$$O(NX + QN / X)$$$. By picking $$$X \sim \sqrt Q$$$, we could achieve a time complexity of $$$O(N\sqrt Q)$$$.

First, for each node we want to find $$$src[i]$$$ : the nearest tree to each node, and $$$ds[i]$$$, the distance to that tree. These can be found via multi-source breadth-first search. To ensure that ties are broken correctly, ensure that $$$T$$$ is sorted in increasing order before entering them in the queue.

Now consider the park to be a tree graph rooted at node $$$1$$$. Let $$$c(u, v)$$$ be the cost of starting from node $$$u$$$ and going to node $$$v$$$ (without considering what the dog does after reaching node $$$v$$$). It is easy to answer $$$c(u, v)$$$ if $$$u$$$ and $$$v$$$ are neighbors in the graph; $$$c(u, v) = 1$$$ if $$$src[u] = src[v]$$$ and $$$ds[u] \gt ds[v]$$$ (because the dog is already chasing in that direction), otherwise $$$c(u, v) = 2 \cdot ds[u] + 1$$$, as the dog has to chase the squirrel before you could bring him back to node $$$u$$$ to step to node $$$v$$$.

It can be seen that for nodes that aren't neighbors $$$u$$$ and $$$v$$$, if the simple path between them is $$$u, p_1, p_2, \ldots, p_m, v$$$, $$$c(u, v) = c(u, p_1) + c(p_1, p_2) + \ldots + c(p_m, v)$$$.

To find arbitrary $$$c(u, v)$$$ quickly, precalculate $$$w_{up}[i]$$$ and $$$w_{dn}[i]$$$, these are cumulative costs for paths going up toward or down from the root of the tree graph. $$$w_{up}[i] = w_{up}[P_i] + c(i, P_i)$$$, and $$$w_{dn}[i] = w_{dn}[P_i] + c(P_i, i)$$$.

To answer a query for $$$x, y$$$, first find $$$l$$$, the lowest common ancestor (LCA) of nodes $$$x$$$ and $$$y$$$, using your favorite method (link, link). Then then answer is given by $$$c(x, y) + (2 \cdot ds[y]) = (w_{up}[x] - w_{up}[l]) + (w_{dn}[y] - w_{dn}[l]) + (2 \cdot ds[y])$$$: the cost of the path from $$$x$$$ upward to $$$l$$$, the path from $$$l$$$ downward to $$$y$$$, and we must not forget to include the last chase at node $$$y$$$.

Note that it is possible to "cheese" subtask 1 if you can spot the method:

Time complexity: $$$O((N+Q) \log N)$$$