À l’Olympiade internationale d’informatique de 20XX, une nouvelle épreuve mixte a été créée. Chaque équipe réunit un garçon et une fille résolvant les problèmes ensemble. Pour constituer la sélection, le comité a choisi $N$ candidats et $M$ candidates. Les garçons sont numérotés de $0$ à $N-1$ et les filles de $0$ à $M-1$.

La force d’une équipe dépend des capacités de conception d’idées et d’implémentation de ses deux membres. Chaque capacité est un entier compris entre $1$ et $10^9$, bornes incluses. Le garçon $i$ a les capacités $A_1[i]$ et $B_1[i]$, respectivement, et la fille $j$ a $A_2[j]$ et $B_2[j]$. La force de leur équipe est définie par $(A_1[i]+A_2[j])\times(B_1[i]+B_2[j])$.

Tous ont été sélectionnés après une compétition acharnée, donc aucun garçon n’en surpasse un autre dans les deux capacités. Plus précisément, la capacité de conception croît strictement avec le numéro et celle d’implémentation décroît strictement : $A_1[i]<A_1[i+1]$ et $B_1[i]>B_1[i+1]$ pour $0\le i\le N-2$. Il en va de même pour les filles : $A_2[j]<A_2[j+1]$ et $B_2[j]>B_2[j+1]$ pour $0\le j\le M-2$.

Le comité veut maximiser la force de l’équipe dans divers scénarios. Il y en a $Q$, numérotés de $0$ à $Q-1$. Dans le scénario $k$, le numéro du garçon doit appartenir à $[L_1[k],R_1[k]]$ et celui de la fille à $[L_2[k],R_2[k]]$, bornes incluses. Écrivez un programme trouvant la force maximale d’une équipe valide pour chaque scénario.

Détails d'implémentation

Implémentez la fonction suivante.

vector<long long> build_teams(vector<int> A1, vector<int> B1, vector<int> A2,
vector<int> B2, vector<int> L1, vector<int> R1, vector<int> L2, vector<int> R2)

• $A_1,B_1$ : Tableaux de longueur $N$. Le garçon $i$ a la capacité de conception $A_1[i]$ et d’implémentation $B_1[i]$ ($0\le i\le N-1$).
• $A_2,B_2$ : Tableaux de longueur $M$. La fille $j$ a la capacité de conception $A_2[j]$ et d’implémentation $B_2[j]$ ($0\le j\le M-1$).
• $L_1,R_1,L_2,R_2$ : Tableaux de longueur $Q$. Dans le scénario $k$, le numéro du garçon doit appartenir à $[L_1[k],R_1[k]]$ et celui de la fille à $[L_2[k],R_2[k]]$ ($0\le k\le Q-1$).
• Renvoyez un tableau $C$ de longueur $Q$, où $C[k]$ est la force maximale d’une équipe dans le scénario $k$.

Aucune partie du code soumis ne doit exécuter de fonction d’entrée ou de sortie.

Contraintes

• $1\le N\le100\,000$
• $1\le M\le100\,000$
• $\forall i\in[0,N-1]:\quad1\le A_1[i],B_1[i]\le10^9$
• $\forall j\in[0,M-1]:\quad1\le A_2[j],B_2[j]\le10^9$
• $\forall i\in[0,N-2]:\quad A_1[i]<A_1[i+1],\ B_1[i]>B_1[i+1]$
• $\forall j\in[0,M-2]:\quad A_2[j]<A_2[j+1],\ B_2[j]>B_2[j+1]$
• $1\le Q\le100\,000$
• $\forall k\in[0,Q-1]:\quad0\le L_1[k]\le R_1[k]\le N-1$
• $\forall k\in[0,Q-1]:\quad0\le L_2[k]\le R_2[k]\le M-1$

Sous-tâches

1. (5) $N\le500,\ M\le500,\ Q\le500$
2. (10) $Q\le20$
3. (10) $\forall k\in[0,Q-1]:\quad L_2[k]=0,\ R_2[k]=M-1$
4. (35) $\forall k\in[0,Q-1]:\quad L_2[k]=R_2[k]$
5. (40) Aucune contrainte supplémentaire.

Exemples

1

Considérons les valeurs suivantes :

$N=5$, $M=4$, $A_1=[2,7,8,9,10]$, $B_1=[10,9,8,6,1]$, $A_2=[1,3,5,9]$, $B_2=[10,8,7,5]$, $Q=3$, $L_1=[0,2,1]$, $R_1=[4,3,1]$, $L_2=[1,0,0]$, $R_2=[3,2,0]$.

Le correcteur appelle la fonction ainsi :

build_teams([2, 7, 8, 9, 10], [10, 9, 8, 6, 1], [1, 3, 5, 9], [10, 8, 7, 5],
[0, 2, 1], [4, 3, 1], [1, 0, 0], [3, 2, 0])

Dans le scénario $0$, le numéro du garçon doit appartenir à $[0,4]$ et celui de la fille à $[1,3]$. Choisir le garçon $1$ et la fille $3$ donne la force $(7+9)\times(9+5)=224$. C’est la force maximale parmi les équipes respectant les conditions.

Dans le scénario $1$, le numéro du garçon doit appartenir à $[2,3]$ et celui de la fille à $[0,2]$. Choisir le garçon $2$ et la fille $2$ donne la force $(8+5)\times(8+7)=195$. C’est la force maximale parmi les équipes respectant les conditions.

Dans le scénario $2$, le numéro du garçon doit appartenir à $[1,1]$ et celui de la fille à $[0,0]$. Choisir le garçon $1$ et la fille $0$ donne la force $(7+1)\times(9+10)=152$.

La fonction doit donc renvoyer $[224,195,152]$.

2

Considérons les valeurs suivantes :

$N=4$, $M=2$, $A_1=[1,6,8,10]$, $B_1=[9,5,3,1]$, $A_2=[5,6]$, $B_2=[8,7]$, $Q=4$, $L_1=[0,1,2,3]$, $R_1=[0,1,2,3]$, $L_2=[0,0,0,0]$, $R_2=[1,1,1,1]$.

Le correcteur appelle la fonction ainsi :

build_teams([1, 6, 8, 10], [9, 5, 3, 1], [5, 6], [8, 7], [0, 1, 2, 3], [0, 1,
2, 3], [0, 0, 0, 0], [1, 1, 1, 1])

Dans le scénario $0$, choisir le garçon $0$ et la fille $1$ donne la force $(1+6)\times(9+7)=112$.

Dans le scénario $1$, choisir le garçon $1$ et la fille $1$ donne la force $(6+6)\times(5+7)=144$.

Dans le scénario $2$, choisir le garçon $2$ et la fille $0$ donne la force $(8+5)\times(3+8)=143$.

Dans le scénario $3$, choisir le garçon $3$ et la fille $0$ donne la force $(10+5)\times(1+8)=135$.

Toutes ces valeurs sont les forces maximales des équipes respectant les conditions de leurs scénarios respectifs. La fonction doit donc renvoyer $[112,144,143,135]$.

Correcteur d’exemple

Le correcteur d’exemple lit l’entrée au format suivant.

• Ligne $1$: $N\ M$
• Ligne $2+i$ ($0\le i\le N-1$): $A_1[i]\ B_1[i]$
• Ligne $2+N+j$ ($0\le j\le M-1$): $A_2[j]\ B_2[j]$
• Ligne $2+N+M$: $Q$
• Ligne $3+N+M+k$ ($0\le k\le Q-1$): $L_1[k]\ R_1[k]\ L_2[k]\ R_2[k]$

Le correcteur d’exemple affiche ce qui suit.

• Ligne $1+k$ ($0\le k\le Q-1$): L’élément d’indice $k$ du tableau renvoyé par build_teams.

Le correcteur d’exemple peut différer de celui utilisé pour l’évaluation réelle.