All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Teleports are magical devices. If there is a teleport located at point (x, y) and has radius R, then it can transport a person from any point (a, b) such that |x-a|+|y-b| ≤ R to any point (c, d) such that |x-c|+|y-d| ≤ R.
Initially there are no teleports. You need to process operations of two types:
- Add a new teleport at the location (x, y)
- Report whether it is possible to reach teleport j from teleport i, where by teleport i, we mean the teleport added during the i-th operation
Note that you can transport from a teleport to a location which does not contain a teleport as well.
- The first line of the input contains two integers, Q, and R, denoting the total number of operations and the radius of each teleport.
- The i-th of the next Q lines contains one operation, which will be one of the following two types:
- + x y — add a new teleport at location (x, y). This teleport will be called teleport i.
- ? i j — Report whether it is possible to reach teleport j from teleport i
For each operation, output a single line containing "DA" (without quotes) if we can reach teleport j from teleport i or "NET" (without quotes) otherwise.
- 1 ≤ Q, R, x, y ≤ 100,000
- It is guaranteed that all operations are valid. In particular, if there is an operation of the form ? i j, then it is guaranteed that the i-th and j-th operations were insert operations.
- Subtask #1 (30 points): 1 ≤ Q ≤ 2000
- Subtask #2 (70 points): Original constraints.
Input: 5 1 + 2 2 + 3 3 ? 1 2 + 100 3 ? 2 4 Output: DA NET
The first two operations make us add teleports at the locations (2, 2) and (3, 3).
Then, we need to find if the 2nd teleport can be reached from the 1st teleport. From teleport at (2, 2) we can reach the point (2, 3) (because |2-2|+|2-3| <=1), and then from the point (2, 3) we can go to (3, 3) by using the teleport at (3, 3) (because |2-3|+|3-3| <= 1). Hence, the answer is DA.
Then we add teleport 4 at (100, 3).
In the last operation, we are asked whether we can reach the teleport at (100, 3) from the teleport at (3, 3). We cannot, and hence the answer is NET.
|Tags||gainullinildar, ltime48, medium-hard, segment-tree, sqrt-decomp|
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, 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, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.