Jotunheim – Épreuve régionale 2024

Niveau 6 ⋅ Validation weight: 20%

Énoncé

Jotunheim est le royaume des géants de glace, ennemis des dieux. Odin veut montrer sa puissance à ses ennemis jurés, pour cela il veut détruire ce royaume petit à petit. Possédant la carte avec les principales villes de ce royaume, il demande l'avis de Jøsëf Marchand afin d'anéantir intelligemment chaque ville du royaume.

La particularité des villes de ce royaume est qu'elles peuvent se déplacer avec les mouvements de la glace. Il faut donc prendre cela en compte dans les calculs de Jøsëf.

Les villes sont représentées par $N$ points $(x, y)$ sur la carte bidimensionnelle.

Odin vous fournit $R$ requêtes :

  1. (type 1) Le royaume se déplace. Avec les paramètres $A$ et $B$ : multiplier tous les $x$ par $A$ et tous les $y$ par $B$.
  2. (type 2) Odin attaque une ville. Avec les paramètres $U$ et $V$ : afficher la ville maximisant $Ux + Vy$. Si plusieurs villes maximisent l'équation, donner la ville avec le plus petit $y$ et la ville avec le plus petit $x$ si les $y$ sont égaux.
  3. (type 3) Le royaume se déplace. Annuler toutes les requêtes de type 1.

Toutes les valeurs sont entières, il est garanti qu'aucune valeur à l'absolue ne dépasse $10^{18}$. De plus, au moins une requête de type 2 est garantie.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de villes.
  • Sur la ligne suivante, un entier : R, le nombre de requêtes d'Odin.
  • Sur les lignes suivantes, une liste de N éléments : villes, les valeurs de chaque villes.
    • Une ligne par élément de la liste : séparés par des espaces, un entier x (première valeur), et un entier y (deuxième valeur).
  • Sur les lignes suivantes, une liste de R éléments : requetes, chaque requête.
    • Une ligne par élément de la liste : séparés par des espaces, un entier type requete (type de la requête (1, 2 ou 3)), un entier param 1 (premier paramètre (A pour type 1, U pour type 2, 0 pour type 3)), et un entier param 2 (deuxième paramètre (B pour type 1, V pour type 2, 0 pour type 3)).

Sortie

Traiter chaque requête d'Odin comme décrit dans l'énoncé

Contraintes

  • $1 \le N \le 10\,000$
  • $1 \le R \le 100\,000$
  • $1 \le \text{type requete} \le 3$
  • $-10\,000 \le \text{param 1}, \text{param 2} \le 10\,000$
  • $-10\,000 \le \text{x}, \text{y} \le 10\,000$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
3
3
1 1
0 1
1 0
2 4 4
1 2 -3
2 3 1
Exemple de sortie
1 1
2 0
Commentaire

Nous avons 3 villes et 3 requêtes à répondre. Voici les requêtes :

  • Type 2, donner la ville maximisant $4x + 4y$ : 1 1 maximise car $4 \times 1 + 4 \times 1 = 8$, les autres villes ont une valeur de $4$.
  • Type 1, les positions des villes sont changées :
  • 1 1 -> 2 -3
  • 0 1 -> 0 -3
  • 1 0 -> 2 0
  • Type 2, donner la ville maximisant $3x + y$ :
  • 2 -3 -> $3 \times 2 - 3 = 3$
  • 0 -3 -> $3 \times 0 - 3 = -3$
  • 2 0 -> $3 \times 2 + 0 = 6$, cette ville maximise.
Exemple d'entrée
5
3
-1 -1
-1 1
1 1
1 -1
0 0
2 1 1
2 1 0
2 0 -1
Exemple de sortie
1 1
1 -1
-1 -1
Exemple d'entrée
2
4
0 1
1 0
1 2 10
2 2 1
3 0 0
2 2 1
Exemple de sortie
0 10
1 0