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
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

The God of Death is a famous assassin. As his student, you are assigned to keep track of N targets, numbered 1, 2, \ldots 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, \ldots, L_N, the locations of the N targets on day 0.
The next line contains 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, 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...