Chef and Frogs
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Nobody knows, but N frogs live in Chef's garden.
Now they are siting on the X-axis and want to speak to each other. One frog can send a message to another one if the distance between them is less or equal to K.
Chef knows all P pairs of frogs, which want to send messages. Help him to define can they or not!Note : More than 1 frog can be on the same point on the X-axis.
- The first line contains three integers N, K and P.
- The second line contains N space-separated integers A1, A2, ..., AN denoting the x-coordinates of frogs".
- Each of the next P lines contains two integers A and B denoting the numbers of frogs according to the input.
- For each pair print "Yes" without a brackets if frogs can speak and "No" if they cannot.
- 1 ≤ N, P ≤ 10^5
- 0 ≤ Ai, K ≤ 10^9
- 1 ≤ A, B ≤ N
Input: 5 3 3 0 3 8 5 12 1 2 1 3 2 5 Output: Yes Yes No
For pair (1, 2) frog 1 can directly speak to the frog 2 as the distance between them is 3 - 0 = 3 <= K .
For pair (1, 3) frog 1 can send a message to frog 2, frog 2 can send it to frog 4 and it can send it to frog 3.
For pair (2, 5) frogs can't send a message under current constraints.
|Tags||berezin, dynamic-programming, july14, simple|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.