THICC '17 P3 - The God of Death

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

The God of Death is a famous assassin. As his student, you are assigned to keep track of N targets, numbered 1, 2, \dots, N. The God of Death will then give you Q queries.

  1. C x y: The x-th target moves to location y. This action marks the beginning of a new day.
  2. Q x y: Return the location of the x-th target on the y-th day. It is guaranteed that if it is currently day d, y \le d.

Can you answer the God of Death's queries?

Input Specification

The first line will contain N.
The next line will contain N integers, L_1, L_2, \dots, L_N, the locations of the N targets on day 0.
The next line will contain Q.
The next Q lines will each contain a valid query, as described above.

Output Specification

Output the answer to each Q query on a new line.


For all subtasks:

1 \le L_i \le 10^9

1 \le x \le N

1 \le Q \le 10^5

Subtask 1 [30%]

1 \le N \le 10^3

Subtask 2 [70%]

1 \le N \le 10^6

Sample Input

2 3 1
C 3 2
C 2 1
Q 1 1
Q 2 2
C 1 3
Q 3 3

Sample Output



  • 0
    Evan_Yu123  commented on Aug. 9, 2017, 7:23 p.m. edited

    For some reason, my O(NQ) algorithm TLEs on all cases, and my O(QlogN) algorithm TLEs on subtask 2, both are written in Java. Is this supposed to happen?

    • 0
      Pleedoh  commented on Aug. 9, 2017, 10:55 p.m.

      Use pairs. If you're using java, make a class for pairs, it's very easy.

    • -1
      TheZombieCloud  commented on Aug. 9, 2017, 8:14 p.m.

      Just wait m8. Imma do this.

      • 0
        Pleedoh  commented on Aug. 9, 2017, 10:57 p.m.

        You're over complicating this...