Nicks Landing

All submissions for this problem are available.
In a city called *Nick's Landing*, there are $N$ people (numbered $1$ through $N$). For each valid $i$, the $i$th person has beauty $B_i$ and politeness $P_i$; no two people are equally beautiful. You should answer $Q$ queries. In each query you are given two integers $L$ and $R$, and you should calculate $Score(L, R)$ as defined below: ``` Score (L, R) : Initialize empty Lists Q, OddQ, EvenQ For each person with id between [L, R] : add his id to List Q Sort Q in increasing order of the beauty value of the persons Flag = 0; For each person's id in Q : Flag = 1  Flag If (Flag == 1) append his id to List OddQ Else append his id to List EvenQ Return DiffSum (OddQ) + DiffSum (EvenQ) DiffSum (Z[1...n]) : Sum = 0 For i = 2 to n : u = Z[i] v = Z[i  1] Sum = Sum + P[u]  P[v] Return Sum ``` ### Input  The first line of the input contains a single integer $N$.  Each of the next $N$ lines contains two spaceseparated integers $B_i$ and $P_i$.  The next line contains a single integer $Q$.  Each of the next $Q$ lines contains two spaceseparated integers $L$ and $R$ describing a query. ### Output For each query, print a single integer(answer to the query) in a single line. ### Constraints  $1 \le N, Q \le 2 \cdot 10^5$  $1 \le B_i, P_i \le 2 \cdot 10^5$  $1 \le L \le R \le N$  All beauty values are **distinct**. ### Example Input ``` 6 2 1 4 6 1 4 3 10 6 4 5 8 5 1 3 1 6 3 6 2 5 4 4 ``` ### Example Output ``` 2 15 10 8 0 ``` ### Explanation For the $2$nd query, $Q= \{1, 2, 3, 4, 5, 6\}$. If we sort them according to the persons's beauty value, then $Q =\{3, 1, 4, 2, 6, 5\}.$ Now, $OddQ = \{3, 4, 6\}$ and $EvenQ = \{1, 2, 5\}$ So, $DiffSum$ $(OddQ) = $ $P_3$  $P_4$ $+$ $P_4$  $P_6$ $=$ $6 + 2$ $=$ $8.$ Similiarly, $DiffSum$ $(EvenQ) =$ $P_1$  $P_2$ $+$ $P_2$  $P_5$ $=$ $5 + 2$ $=$ $7.$ So $Score = 7 + 8 = 15.$Author:  msi_cse_buet 
Tags  msi_cse_buet 
Date Added:  5122019 
Time Limit:  6 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, 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. 