Pizza Delivery

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Flatland is a 1D country — all points in Flatland lie on one line. Everybody in Flatland loves pizza (because it's flat enough). There are $n$ pizzerias numbered $1$ through $n$, which serve $m$ consumers numbered $1$ through $m$. Let's denote the position of the $i$th pizzeria by $s_i$ and the position of the $i$th consumer's home by $c_i$. No two pizzerias are located at the same position, but the position of any consumer can coincide with the position of any pizzeria or consumer. Every consumer wants to order one pizza, spending as little money as possible. The $i$th pizzeria sells each pizza at a certain baseline price $p_i$; delivering pizza from point $x_1$ to point $x_2$ costs an additional $(x_1  x_2) ^ 2$. These prices are independent — even if multiple pizzas can be delivered at once, each consumer needs to pay the full price for their delivery. Unfortunately, some consumers don't like some pizzerias, so they won't order pizza from them. Specifically, for each consumer, you are given a list of pizzerias this consumer won't order from no matter what. For each consumer, find the amount of money they will spend for the pizza with delivery. ### Input  The first line of the input contains two spaceseparated integers $n$ and $m$ denoting the number of pizzerias and the number of consumers.  For each $i$ ($1 \le i \le n$), the $i$th of the following $n$ lines contains two spaceseparated integers $s_i$ and $p_i$.  For each $i$ ($1 \le i \le m$), the $i$th of the following $m$ lines contains two spaceseparated integers $c_i$ and $k_i$, followed by a space (if $k_i \gt 0$) and $k_i$ spaceseparated integers $d_{i, 1}, d_{i, 2}, \dots, d_{i, k_i}$ denoting the list of pizzerias the $i$th consumer won't order from. ### Output Print $m$ lines. For each $i$ ($1 \le i \le m$), the $i$th of these lines should contain a single integer — the amount of money the $i$th consumer will spend. ### Constraints  $1 \le n, m \le 200,000$  $0 \le s_i, c_i \le 10^9$ for each valid $i$  $1 \le p_i \le 10^9$ for each valid $i$  $0 \le k_i \le n1$ for each valid $i$  $0 \le \sum_{i=1}^m k_i \le 400,000$  $1 \le d_{i, j} \le n$ for each valid $i, j$  $s_1, s_2, \dots, s_n$ are pairwise distinct ### Subtasks **Subtask #1 (15 points):** $n, m \le 1,000$ **Subtask #2 (35 points):** $k_i = 0$ for each valid $i$ **Subtask #3 (50 points):** original constraints ### Example Input ``` 3 3 1 7 10 5 8 9 3 0 3 1 1 6 2 1 2 ``` ### Example Output ``` 11 34 13 ``` ### Explanation The first consumer likes all the pizzerias, so they order a pizza from the first pizzeria, since it will cost the least, $7 + (3  1)^2 = 11$. The second consumer doesn't like the first pizzeria, so they won't order from there, even though it's the cheapest option. Therefore, they order a pizza from the third pizzeria. It costs $9 + (8  3)^2 = 34$. The third consumer likes only the third pizzeria, so they order from there. It costs $9 + (8  6)^2 = 13$.Author:  qoo2p5 
Editorial  https://discuss.codechef.com/problems/PDELIV 
Tags  july18, mediumhard, qoo2p5 
Date Added:  8062018 
Time Limit:  2 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions