Devu and Manhattan Distance
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Devu has taken the course of computational geometry in the university of Coderpur. He liked this course very much. Today, he got to know about the Manhattan distance and got an assignment for the same topic. Manhattan distance between two points (x1,y1) and (x2,y2) can be defined as:
Manhattan Distance = abs(x1-x2) + abs(y1-y2)
Devu has N points in the Co-ordinate plane. Co-ordinate of ith point is (xi,yi). Points are indexed from 0 to (N-1)(both inclusive).
He has Q updates or queries, for each update U[i, x,y], change the co-ordinate of ith point to (x,y).
For each query [L,R], find pair of points whose indices are between L and R(both inclusive) , such that Manhattan distance between them is maximized. Report the maximum Manhattan distance for each of the query.
Devu has to submit the assignment on the Monday, so help him in solving the problem.
- First line of the input will contain an integer N denoting the number of the points in Cartesian plane.
- Next N lines will be containing the co-ordinates of the N points.
- Next line will contain an integer Q denoting the number of the queries.
- Next Q lines will be containing character 'Q' followed by pair of indices for each of the query or 'U' followed by value of i,x and y for the update.
For each query, print a single integer representing the answer of that query.
- 0 ≤ L ≤ R ≤ N-1
- -109 ≤ x,y ≤ 109
Subtask #1: 20 points
- 1 ≤ N,Q ≤1000.
Subtask #3: 80 points
- 1 ≤ N,Q ≤ 105
Input: 4 10 10 10 20 20 20 20 10 2 U 1 20 20 Q 0 3 Output: 20
After first updates points will be:
So, maximum Manhattan distance will be between points (10,10) and (20,20), which will be 20.
|Tags||amitpandeykgp, easy, ltime24, segment-tree|
|Time Limit:||1 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.