THICC '17 P3 - The God of Death

View as PDF

Submit solution


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

Author:
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.

Constraints

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

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

Sample Output

2
1
2

Comments


  • 0
    Evan_Yu123  commented on Aug. 9, 2017, 11:23 p.m. edit 2

    For some reason, my \mathcal{O}(NQ) algorithm TLEs on all cases, and my \mathcal{O}(Q \log N) algorithm TLEs on subtask 2, both are written in Java. Is this supposed to happen?


    • 0
      Pleedoh  commented on Aug. 10, 2017, 2:55 a.m.

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