Une maison Minecraft#12216

Une maison Minecraft (Corrigé)

Auteur du problème:	De3b0o
Préparé par:	De3b0o
Édité par:	Hasan Saleh (MathModel)

Solution

Tout au long de la solution, nous allons supposer que $n \leq m$ n \le m, sinon nous pouvons simplement faire pivoter la grille.

Nous ne pouvons pas nous permettre de simuler chaque requête cellule par cellule. Au lieu de cela, nous traitons ligne par ligne.

Pour une ligne fixe $i$ , considérons une requête $(x, y, d, c, s)$ (x,y,d,c,s). Toutes les cellules qui satisfont la première condition (la condition de distance) forment un intervalle $[l, r]$ [l,r].

Ainsi, chaque requête ajoute un intervalle à la ligne $i$ .

Nous pouvons utiliser une approche de ligne de balayage pour calculer toutes les valeurs du tableau $b$ pour la ligne $i$ .

Pour la ligne $i$ , nous créons des événements à $l$ et $r + 1$ r+1 pour l'intervalle $[l, r]$ [l,r]. Chaque événement signifie : "commencer à ajouter cette requête" ou "arrêter d'ajouter cette requête".

Nous maintenons un tableau de fréquence $f [c]$ = total $s$ des requêtes actives avec le paramètre $c$ . Nous maintenons également $s u m =$ somme de tous les $s$ actifs.

Lors du traitement de la ligne $i$ et de la colonne $j$ :

Si $a_{i, j} = 0$ a_{i,j}=0, alors $b_{i, j} = s u m$ b_{i,j}=sum.
Sinon, pour chaque diviseur $d$ de $a_{i, j}$ a_{i,j}, ajoutez $f [d]$ à $b_{i, j}$ b_{i,j}.

En conclusion :

nous itérons sur toutes les lignes ( $1 \leq i \leq n$ 1 \le i \le n), pour chaque ligne nous itérons sur toutes les requêtes et trouvons l'intervalle $[l, r]$ [l,r] pour chaque requête, puis en utilisant une approche de ligne de balayage, nous pouvons déterminer les valeurs du tableau $b$ pour cette ligne.

Complexité :

Précomputation des diviseurs : $O (n \cdot m \cdot max A)$ \mathcal{O}(n \cdot m \cdot \sqrt{\max A}).
Pour chaque ligne, nous itérons sur toutes les requêtes donc c'est $O (n \cdot q)$ \mathcal{O}(n \cdot q).
Pour chaque cellule $(x, y)$ , nous itérons sur tous les diviseurs de $a_{x, y}$ a_{x,y} donc c'est $O (n \cdot m \cdot max D)$ \mathcal{O}(n \cdot m \cdot \max D).

La complexité totale est $O (n \cdot m \cdot (max A + max D) + n \cdot q)$ \mathcal{O}(n \cdot m \cdot (\sqrt{\max A} + \max D) + n \cdot q), et puisque $n \leq m$ n \le m, alors $n \leq (n \cdot m) \leq 320$ n \le \sqrt(n \cdot m) \le 320, $max A$ <= $1 0^{6}$ 10^6, $max D = 240$ \max D = 240.

Rendant la pire complexité totale $O (3 e 8)$ ce qui passe en moins de 4 secondes.

Voici l'implémentation :


// Code C++ ici