GemNuAi

Gem nu ai că ești sărac, dar îți place să gătești. Ești mega chef. Ai pretenții și gătești doar cu cuțite de aur. Asta nu este doar povestea ta, este povestea a $N$ chefi numerotați de la $0$ la $N-1$ (sortați după cât de în sânge fac ei carnea). Pentru fiecare astfel de chef se cunosc $2$ intervale, cheful $i$ fiind reprezentat de intervalele $[A_i, B_i]$, respectiv $[C_i, D_i]$. Aceste intervale sunt reprezentate pe axa culinară cu valori de la $1$ la $N$, unde fiecare element reprezintă un tip de mâncare (sau un dish cum spun englezii). Pentru fiecare chef $i$, se știe că el poate să pregătească orice dish din intervalul $[A_i, B_i]$, dar în eventualitatea în care participă la un concurs internațional culinar (foarte puțin probabil), acesta dorește să pregătească pentru concurs dish-urile din intervalul $[C_i, D_i]$ (și știi cum e în viață, ce poți nu e mereu ce vrei).

Și pac urmează o competiție internațională culinară (cine se aștepta?) numită Șiaorma Fest, că dacă nu urma, nu o menționam. Chefii au început să facă echipe, iar bârfele sunt pe val. Există $2$ criterii mari și late pentru ca un subset de chefi să poată să facă echipă:

• Aceștia să reprezinte un interval compact de indici. De exemplu, cheful cu indicele $3$ poate să facă echipă cu cheful cu indicele $6$ doar dacă se bagă în echipă și chefii $4$ și $5$. Nu de alta, dar cheful $3$ care face carnea mai în sânge nu face echipa cu orice demodat cu indicele $6$ care face carnea mai "uel dan", decât dacă sunt în echipă și toți ceilalți chefi intermediari să medieze conflictul și să nu se certe până se termină timpul.

• În plus, un interval de chefi $[x,y]$ pot face echipă dacă pentru fiecare chef $i$ din echipă și pentru fiecare dish $j$ din intervalul $[C_i, D_i]$, există cel puțin un chef $k$ din echipă ($k$ poate să fie egal cu $i$) care poate să gătească dish-ul $j$.

Cerință

Se dau $Q$ interogări, fiecare interogare constând în doi indici $x$ și $y$. Pentru fiecare interogare, se cere să se determine dacă subsecvența $[x, y]$ de chefi pot să facă echipă sau nu.

În funcție de cât de skillat te simți, poți alege să răspunzi la aceste query-uri offline (cerința $1$) sau online (cerința $2$) și vei primi puncte pe măsură.

Detalii de implementare

Va trebui să implementezi mai multe funcții. Prima dintre ele este:

int precompute(int N, int Q, std::vector<int> A, std::vector<int> B, std::vector<int> C, std::vector<int> D)

care primește ca parametri:

• $N$, numărul total de chefi
• $Q$, numărul de interogări
• $A, B, C$ și $D$, vectori cu semnificația din enunț

Funcția precompute trebuie să proceseze datele primite și apoi să returneze o valoare din mulțimea $\{1, 2\}$ în funcție de cerința pe care alegeți să o rezolvați. În continuare, va trebui să implementați câte o funcție pentru fiecare cerință, numite cerinta_1 și cerinta_2.

std::vector<bool> cerinta_1(std::vector<std::pair<int, int>> queries)

care:

• primește ca parametru queries, un vector indexat de la care conține cele $Q$ interogări;
• returnează un vector de lungime $Q$ în care pe poziția $i$ se va afla răspunsul la a $i$-a interogare pentru $0 \leq i < N$.

bool cerinta_2(std::pair<int, int> query)

care:

• primește ca parametru query, o pereche reprezentând o singură interogare;
• returnează true dacă răspunsul la interogare este pozitiv și false altfel.

Pentru un test în care funcția precompute a returnat valoarea:

• $1 \ -$ funcția cerinta_1 va fi apelată o singură dată;
• $2 \ -$ funcția cerinta_2 va fi apelată de $Q$ ori.

Observați că dacă întotdeauna optați pentru aceeași cerință, atunci nu este obligatoriu să implementați o soluție valida pentru ambele cazuri, dar tot va trebui să includeți o definiție a funcției. Vedeți modelul din sample-solution.cpp.

Restricții și precizări

• $1 \leq N \leq 500 \ 000$.
• $1 \leq Q \leq 5 \ 000 \ 000$.
• $1 \leq A_i \leq B_i \leq N$.
• $1 \leq C_i \leq D_i \leq N$.
• $0 \leq L_i \leq R_i < N$.
• Pentru rezolvarea cerinței $1$ se acordă $70\%$ din punctajul testului.

Exemplul 1

input

10 3
1 3 1 2 1 1 1 1 2 1
3 3 3 2 2 1 2 2 3 3
1 1 2 1 1 1 2 1 2 1
1 3 2 2 1 3 2 1 2 2
2 4
5 7
7 9

output

query 0: 1
query 1: 0
query 2: 1

Explicație

Chefii din subsecvența $[2, 4]$ pot să pregătească împreună dish-urile $\{1, 2, 3\}$, prin urmare ei pot fi parte din aceeași echipă.

Chefii din subsecvența $[5, 7]$ nu pot să pregătească împreună dish-urile $\{1, 2\}$, care nu acoperă complet intervalul $[C_5, D_5]$