Fişierul intrare/ieşire:trampoline.in, trampoline.outSursăInfo(1)cup 2020
AutorAlexa TudoseAdăugată deAlexa2001Alexa Tudose Alexa2001
Timp execuţie pe test2 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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 la C.

Profesoara lui Pătrăţel i-a cerut să încerce T exerciţii. Al i-lea exerciţiu are următoarele reguli:

  • Exerciţiul începe la trambulina (xistart, yistart).
  • Exerciţiul se încheie la trambulina (xistop, yistop).
  • 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.
  • 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.

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 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 xistart, yistart, xistop, yistop.

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.

Restrictii

  • 1 ≤ R, C ≤ 1.000.000.000
  • 1 ≤ N, T ≤ 200.000
  • 1 ≤ xistart, xistop ≤ R
  • 1 ≤ yistart, yistop ≤ 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, xistop - xistart = 1
  • Pentru 19 puncte, 1 ≤ T, N ≤ 5.000

Exemple

trampoline.intrampoline.out
4 5 2
2 2
3 4
3
2 1 4 5
1 2 1 4
2 3 4 4
Yes
Yes
No

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?