THICC '17 P3 - The God of Death - Olympiads Online Judge

THICC '17 P3 - The God of Death

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$ ~N~ targets, numbered $1, 2, \dots, N$ ~1, 2, \dots, N~. The God of Death will then give you $Q$ ~Q~ queries.

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

Can you answer the God of Death's queries?

Input Specification

The first line will contain $N$ ~N~.
The next line will contain $N$ ~N~ integers, $L_1, L_2, \dots, L_N$ ~L_1, L_2, \dots, L_N~, the locations of the $N$ ~N~ targets on day 0.
The next line will contain $Q$ ~Q~.
The next $Q$ ~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 L_i \le 10^9~

$1 \le x \le N$ ~1 \le x \le N~

$1 \le Q \le 10^5$ ~1 \le Q \le 10^5~

Subtask 1 [30%]

$1 \le N \le 10^3$ ~1 \le N \le 10^3~

Subtask 2 [70%]

$1 \le N \le 10^6$ ~1 \le N \le 10^6~

Sample Input

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)$ ~\mathcal{O}(NQ)~ algorithm TLEs on all cases, and my $\mathcal{O}(Q \log N)$ ~\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.