International OJ

Computing completion times

Let $F_i$ be the completion time of the last submission ever inserted into server $i$. When a submission with judging time $y$ is inserted into server $i$ at time $t$, its start and completion times are

$$\mathrm{start}=\max(t,F_i),\qquad \mathrm{finish}=\max(t,F_i)+y.$$

Then update $F_i$ to the new completion time. Because each server processes its queue in FIFO order, the actual queue does not have to be stored.

Different servers work simultaneously, so submission-query order and completion order may differ. Store every completion event in a min-heap ordered by completion time. Before processing a query at time $t$, pop and apply every event whose completion time is at most $t$.

Completion times can become much larger than the input bound on $t$. Many submissions of judging time $10^9$ can wait on one server, so completion times must be stored in 64-bit integers.

Per-problem ranking

The comparison key of a completed submission is

$$(\mathrm{judgeTime},\ \mathrm{finishTime},\ \mathrm{submissionOrder}).$$

Only the best $5$ submissions of each problem are ever needed. For every problem, keep a sorted vector containing at most those $5$ records. Insert a newly completed record, sort the vector, and remove the last record if the size becomes $6$.

A record that has already fallen out of the best $5$ can never return later, because inserting additional records cannot improve its relative position. Therefore each problem stores only $O(1)$ records.

User ranking

For every user $u$, maintain:

• $C_u$: the current number of solved problems;
• $A_u$: the time at which the user achieved the current solved count.

The user-ranking key is

$$(-C_u,\ A_u,\ \mathrm{nickname}).$$

Store these keys in a std::set; iterating from the beginning gives the ranking order.

When a user solves a new problem for the first time, remove the old key, increase $C_u$ by one, set $A_u$ to that submission's completion time, and insert the new key.

Multiple submissions by the same user to the same problem must increase the solved count only once. Store completed $(\mathrm{user},\mathrm{problem})$ pairs in a hash set, and update the user ranking only when a pair is inserted for the first time. The duplicate check must be made at completion time, not at submission time: a later submission to the same problem may finish earlier on another server.

Every completed submission is still inserted independently into the per-problem ranking.

Processing queries

For a query at time $t$, first apply all completion events with completion time at most $t$.

• For type $1$, compute the new completion time using the server's last completion time and push the event into the min-heap.
• For type $2$, print the stored best records of the requested problem.
• For type $3$, print at most the first $5$ entries of the user-ranking set.

Subtasks

For subtask 1, it is sufficient to rescan and sort all relevant completed submissions for every output query. Since the aggregate $Q$ is at most $2\,000$, an $O(Q^2\log Q)$ solution fits.

For subtask 2, there is only one server and no type-$3$ query. Completion order equals submission order, so a queue of completion events and the best $5$ records of each problem are enough.

For subtask 3, no user ranking is needed. Use a min-heap for completion events and maintain only the best $5$ records per problem.

For subtask 4, there is one server, no type-$2$ query, and every $(\mathrm{nickname},\mathrm{problem})$ pair is submitted at most once. A queue of completion events and the user-ranking set are sufficient.

For subtask 5, every $(\mathrm{nickname},\mathrm{problem})$ pair is unique, so the completed-pair hash set is unnecessary. Maintain the event heap, per-problem top $5$, and user-ranking set.

For the full constraints, add the completed $(\mathrm{user},\mathrm{problem})$ hash set.

Complexity

Each submission is inserted into and removed from the completion-event heap once. User-ranking updates cost $O(\log Q)$, while updating a per-problem vector of size at most $6$ costs $O(1)$.

The complexity of one test case is $O((N+Q)\log Q)$ time and $O(N+Q)$ memory. The aggregate bounds $\sum N,\sum Q\le 200\,000$ keep the total workload within the limits.

Solution written by GPT5.6