Most Distant Points
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Let's consider a set of points S. Initially, S is an empty set. Your task is to implement a data structure that can process the following queries efficiently:
- "+ X Y" - add a new point P with coordinates (X, Y) to S. It's guaranteed that this point will not be in S.
- "- N" - remove a point that was added during the N'th adding query from S. All of the adding queries are numbered in the order of their appearance starting from 1 (queries of other types are not included). It's guaranteed that this point is in S.
- "? X Y" - calculate the maximal Manhattan distance between a point P with coordinates (X, Y) and any point from S. It's guaranteed that S will not be empty.
In addition, you won't be given the exact query data, but instead should decode it in the following way:
Let's store the result of the last processed query of the third type in a variable called ANSWER. Initially, ANSWER is equal to 0. You will be given X', Y' and N' instead of the real values of X, Y and N. To get the real data you should perform the following computations:
- X = X' xor ANSWER;
- Y = Y' xor ANSWER;
- N = N' xor ANSWER.
Don't forget to update the value of ANSWER after processing each query of the third type.
Maybe some of you aren't familiar with some terms in the statement. Here are some articles that could help you understand the problem correctly:
- XOR operation: http://en.wikipedia.org/wiki/Exclusive_or
- Manhattan distance: http://en.wikipedia.org/wiki/Taxicab_geometry
The first line of the input contains one integer Q denoting the number of queries to process.
Each of the next Q lines contains a query to process in the format described above.
For each query on the third type you should output your answer on a new line.
1 ≤ Q ≤ 500,000(5 × 105);
0 ≤ X', Y', N' < 231 for each query;
0 ≤ X, Y ≤ 109 for each query.
Input: 10 + 8 1 - 1 + 3 9 ? 8 4 ? 8 8 ? 12 0 + 6 5 ? 7 8 ? 4 5 - 9 Output: 10 8 2 4 11
Here's a non-encrypted version of the example:
10 + 8 1 - 1 + 3 9 ? 8 4 ? 2 2 ? 4 8 + 4 7 ? 5 10 ? 0 1 - 2
The answers are the same.
|Tags||cook52, easy, geometry, heap, kostya_by, manhattan|
|Time Limit:||1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.