Teleports

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 xa+yb ≤ R to any point (c, d) such that xc+yd ≤ 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 ith operation
Note that you can transport from a teleport to a location which does not contain a teleport as well.
Input
 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 ith 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
Output
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.
Constraints
 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 ith and jth operations were insert operations.
Subtasks
 Subtask #1 (30 points): 1 ≤ Q ≤ 2000
 Subtask #2 (70 points): Original constraints.
Example
Input: 5 1 + 2 2 + 3 3 ? 1 2 + 100 3 ? 2 4 Output: DA NET
Explanation
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 22+23 <=1), and then from the point (2, 3) we can go to (3, 3) by using the teleport at (3, 3) (because 23+33 <= 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.
Author:  gainullinildar 
Tester:  melfice 
Editorial  https://discuss.codechef.com/problems/TELEPORT 
Tags  gainullinildar, ltime48, mediumhard, segmenttree, sqrtdecomp 
Date Added:  26052017 
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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 