|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
E - Enjoy the Chat Group
Languages: C, C++, Java, Python, Kotlin, C#
Time & Memory limits: (details)
You're working on a read notifications feature for your very popular group chat app. The main idea is to show a small rounded icon containing the viewer's profile picture below the messages they have read. Given that everyone is eventually expected to read all messages, your team decided on the following rules for the feature:
- There can never be duplicated icons among the messages.
- If a viewer has read multiple messages, their icon will be docked to the last message (in chronological order) that they read.
- If multiple icons must be displayed for any particular message, then they will be displayed in sorted order by the viewers' ids.
- A viewer cannot ever see their own icon in any message.
You know the time at which each message is sent. You may assume that communication is perfect and that every message is delivered to every user at exactly the same time. Given an access time $T_q$ and a viewer $V_q$, return the ids of the users whose icons must be shown to user $V_q$ for the message that was sent closest to the access time $T_q$.
Input
The first line contains the number of messages $n$ ($1 \leq n \leq 2 \times 10^5$) that were sent in the group and the number of users $v$ ($1 \leq v \leq 2 \times 10^5$) in the group.
The second line contains $n$ sorted distinct integers $tm_i$ ($1 \leq tm_i \leq 10^9$). The $i$-th of them represents the time at which the $i$-th message was sent.
The third line contains the number of accesses to the group's messages $m$ ($1 \leq m \leq 2 \times 10^5$).
The next $m$ lines contain two space-separated integers $v_i$ ($1 \leq v_i \leq v$) and $t_i$ ($1 \leq t_i \leq 10^9$) representing that the $i$-th access was performed by viewer $v_i$ at time $t_i$.
The last line contains two space separated integers $V_q$ ($1 \leq V_q \leq v$) and $T_q$ ($1 \leq T_q \leq 10^9$): $V_q$ is the viewer for which we must display read notification icons and $T_q$ is the time at which this viewer accesses the group chat. Note that this access may or may not appear in the list $m$ of accesses described above.}
Output
Print $K$ space-separated integers in ascending order in a single line. They correspond to the ids of the $K$ viewers whose read notification icons must be shown for the message closest in time to $T_q$ for the given viewer. If there are no ids to write, print "Nothing to display".
Sample test(s)
Input
5 3
1 3 5 7 11
7
1 2
1 3
1 4
2 3
2 5
3 1
3 2
1 4
Output
2
Input
5 3
1 3 5 7 11
7
1 5
1 6
1 7
2 1
2 2
2 3
3 11
2 1
Output
Nothing to display
Input
6 5
1 2 3 5 8 13
7
4 8
4 9
4 10
1 8
2 8
3 10
5 8
1 9
Output
2 4 5