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 \leq 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 \leq L_{i} \leq 10^{9}$

$1 \le x \le N$ $1 \leq x \leq N$

$1 \le Q \le 10^5$ $1 \leq Q \leq 10^{5}$

Subtask 1 [30%]

$1 \le N \le 10^3$ $1 \leq N \leq 10^{3}$

Subtask 2 [70%]

$1 \le N \le 10^6$ $1 \leq N \leq 10^{6}$

Sample Input

Copy

Sample Output

Copy

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