All submissions for this problem are available.
For this not so interesting problem, you are given N intervals.
Each interval has two parameters L and R denoting left and right end-points of the interval. (L ≤ R)
You have to answer Q queries. Each query has two parameters A and B.
For each query, goal is to the find minimum possible value of magic.
Magic for a given query is calculated as follows.
magic = 0
for i in range(0, N)
x = choose any point which lies in ith interval (x ≥ L[i] and x ≤ R[i])
y = choose A or B
magic += |x – y|
Input FormatFirst line of input contains N, the number of intervals.
Next N lines, each contains two integers L and R.
Next line has Q, the number of queries.
Next Q lines, each contains two integers A and B.
Output FormatOutput Q lines, where ith line contains minimum possible value of magic for ith query.
- 1 ≤ N ≤ 2 * 105
- 1 ≤ L ≤ R ≤ 5 * 108
- 1 ≤ Q ≤ 105
- 1 ≤ A, B ≤ 5 * 108
Sample Input 1:2
Sample Input 2:3
|Tags||ipc15flb, medium, segment-tree, skullcrackers|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, PAS fpc, PAS gpc, RUBY, PHP, 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