DMOPC '16 Contest 4 P3 - Carnival Phantasm

View as PDF
Submit solution
Points: 10
Time limit: 1.0s
Memory limit: 256M
Authors:
Phoenix1369, Kirito
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

Molly, having finished the DMOPC, decides to go to a carnival! Noticing the candy apples on sale, Molly checks a map and finds the distance from the entrance to each stand, as well as which candy apples they're selling. Using the skills she has acquired from the DMOPC, she decides to model the stores as such:

  • A x k: The stand x now sells candy apple k.
  • S x k: The stand x no longer sells candy apple k, if it was previously doing so.
  • E x k: The stand x has decided to move locations, and is now a distance of k from the entrance. In addition, it is no longer selling any candy apples.
  • Q k: Print the closest stand that sells candy apple k, or -1 if it doesn't exist.

While Molly is perfectly capable of doing this herself, you also want some candy apples, and this might just be the perfect bribe...

Input Specification

Line 1: Two separated integers, N, and S, the number of stalls, and number of stalls that sell candy apples.

Line 2: N space separated integers d_i, the distance from the entrance to stall d_i.

Lines 3 \dots S + 2 : Two space separated integers, s_i and a_i, indicating that stall s_i sells candy apples of flavour a_i.

Line S + 3: An integer, Q, the number of queries Molly has.

Lines S + 4 \dots S + Q + 3: Any valid query, as described above.

Output Specification

For each Q query, print the answer on a new line.

Constraints

1 \le N, S \le 10^5

1 \le d_i \le 10^9

1 \le s_i \le N

0 \le a_i < 100

1 \le Q \le 10^4

In the case of ties, print the stand with the smaller id.

Sample Input

5 3
1 2 3 4 5
2 1
3 1
5 3
4
Q 1
Q 3
S 2 1
Q 1

Sample Output

2
5
3

Comments


  • 0
    julian33  commented on Jan. 2, 2021, 6:57 p.m.

    Constraints on k are incorrect, please fix


  • 18
    IanWong  commented on Feb. 15, 2017, 10:18 a.m.

    Now you changed 0 <= a[i] < N. SERIOUSLY ? You guys didn't even comment or notice me the constraints are changed. I don't think this is appropriate. You just changed the constraints secretly and act like nothing had happened. I am very disappointed.


    • 10
      r3mark  commented on Feb. 15, 2017, 11:09 a.m.

      Kirito must now commit harakiri in apology.


      • -7
        Kirito  commented on Feb. 15, 2017, 11:28 a.m. ← edited

        This comment is hidden due to too much negative feedback. Click here to view it.


  • 1
    IanWong  commented on Feb. 15, 2017, 9:15 a.m.

    Seems like the constraints is wrong ?? Look at my latest submission.


  • 1
    arknave  commented on Feb. 15, 2017, 3:38 a.m. ← edited

    What do we print, the ID of the nearest stall or the distance to the nearest stall? These are the same in the sample I/O.

    EDIT: reread the constraints, "print the stand with the smaller ID" clears it up.


  • 7
    Sirkular  commented on Feb. 14, 2017, 9:26 p.m.

    N space separated integers di, the distance from the entrance to stall di.

    Do you mean to stall i?


  • 1
    pls  commented on Feb. 14, 2017, 8:31 p.m.

    Can stands sell more than one type of apple?


    • 0
      r3mark  commented on Feb. 14, 2017, 8:40 p.m.

      Yes.


  • 0
    BillZeng2k  commented on Feb. 14, 2017, 4:36 p.m.

    Sorry but can you clarify the constraints on k? Is it also < 100?


    • 0
      Kirito  commented on Feb. 14, 2017, 5:00 p.m.

      Yes.