infoarena informatica de performanta

Bad macro "include(page="template/taskheader" task_id="trampoline") == Pătrăţel a început să sară pe trambuline în sala de sport. În sala de sport sunt $R * C$ trambuline aşezate într-un caroiaj dreptunghiular cu $R$ linii şi $C$ coloane. Fiecare trambulină este fie albastră, fie verde. Printre acestea sunt exact $N$ trambuline verzi. Spunem că $(i, j)$ reprezintă trambulina de pe linia $i$ şi coloana $j$. Indexăm liniile de la $1$ la $R$ şi coloanele de la $1$ se la $C$. Profesoara lui Pătrăţel i-a cerut să încerce $T$ exerciţii. Al $i$-lea exerciţiu are următoarele reguli: \item Exerciţiul începe la trambulina $(x_i^start^, y_i^start^)$. \item Exerciţiul se încheie la trambulina $(x_i^stop^, y_i^stop^)$. \item Daca Pătrăţel sare pe o trambulina verde la pozitia $(i, j)$, atunci poate să sară mai departe fie pe trambulina $(i+1, j)$, fie pe trambulina $(i, j+1)$, cât timp acestea nu sunt în afara caroiajului. \item Daca Pătrăţel sare pe o trambulina albastră la pozitia $(i, j)$, atunci poate să sară mai departe pe trambulina $(i, j+1)$, cât timp aceasta nu este în afara caroiajului. Pătrăţel vrea să afle, pentru fiecare exerciţiu, daca este posibil sa facă ce i-a cerut profesoara. h2. Fisierul de intrare Pe prima linie a fisierului de intrare $trampoline.in" se vor găsi $R$, $C$ şi $N$. Pe următoarele$N$ linii se vor găsi poziţiile trambulinelor verzi. Dacă o linie conţine numerele \texttt{a b} atunci există o trambulina verde la pozitia $(a, b)$. Pe următoarea linie se va găsi numărul $T$. Pe următoarele $T$ se vor găsi descrierile exerciţiilor. Pe a $i$-a linie dintre acestea se vor găsi $x_i^start^$, $y_i^start^$, $x_i^stop^$, $y_i^stop^$. h2. Fisierul de iesire In fisierul de iesire $trampoline.out$ se vor afişa $T$ linii. Pe linia $i$ se afişează $Yes$ daca este posibil cel de al $i$-lea exerciţiu şi $No$ daca nu este posibil. h2. Restrictii * $1 ≤ R, C ≤ 1.000.000.000$ * $1 ≤ N, T ≤ 200.000$ * $1 ≤ x_i^start^, x_i^stop^ ≤ R$, * $1 ≤ y_i^start^, y_i^stop^ ≤ C$, * Coordonatele trambulinelor verzi sunt distincte două câte două. * Pentru $23$ de puncte, $1 ≤ R, C, T≤ 200$ * Pentru $20$ de puncte, $1 ≤ R, C ≤ 2.500, 1 ≤ T ≤ 4.000$ * Pentru $11$ puncte, $x_i^stop^ - x_i^start^ = 1$ * Pentru $19$ puncte, $1 ≤ T, N ≤ 5.000$ h2. Exemple table(example). |_. trampoline.in |_. trampoline.out | | 4 5 2 2 2 3 4 3 2 1 4 5 1 2 1 4 2 3 4 4 | Yes Yes No | h3. Explicatie În primul exerciţiu, Pătrăţel poate urmări următorul drum: $(2, 1) -> (2, 2) -> (3, 2) -> (3, 3) -> (3, 4) -> (4, 4) -> (4, 5)$. În al doilea exerciţiu, Pătrăţel poate urmări următorul drum: $(1, 2) -> (1, 3) -> (1, 4)$. Al treilea exerciţiu este imposibil. Niciun drum de la $(2, 3)$ la $(4, 4)$ nu respectă condiţiile impuse de profesoara lui Pătrăţel. == include(page="template/taskfooter" task_id="trampoline")"