Pour montrer leur esprit festif, les vaches veulent peindre ! Leur image est une grille $R$ $\times$ $C$ $(1 \le R \le 50,000; 1 \le C \le 15)$ de carrés unités, chacun0 ou1. Les lignes sont numérotées $1,\ldots,R$ et les colonnes $1,\ldots,C$.
Pressées, elles demandent l’aide des voisins au nord de la frontière. Sous l’aimable supervision de l’élan Canmuu, elles construisent une machine projetant des seaux entiers de peinture ! La grille commence toute à0 et la machine peint un rectangle en0 ou1. Canmuu propose $Q$ opérations $(1 \le Q \le 10,000)$ ; l’opération $i$ est donnée par cinq entiers $R1_{i}$, $R2_{i}$, $C1_{i}$, $C2_{i}$, $X_{i}$ $(1 \le R1_i \le R2_i \le R; 1 \le C1_i \le C2_i \le C; 0 \le X_{i} \le 1)$ et peint en $X_{i}$ toutes les cases des lignes $R1_{i}$ à $R2_{i}$ et colonnes $C1_{i}$ à $C2_{i}$, bornes incluses.
Cette méthode étant sujette aux erreurs, Canmuu vous demande le nombre de carrés de la bonne couleur après chaque opération.
Limite de mémoire :64 MB
Limite de temps :1.5 seconde
Entrée
- Ligne1 : trois entiers séparés par des espaces $R$, $C$, $Q$.
- Lignes $2,\ldots,R+1$ : ligne $i+1$ contient $C$ caractères '0' ou '1', décrivant la ligne $i$ de la grille.
- Lignes $R+2,\ldots,R+Q+1$ : ligne $R+i+1$ contient cinq entiers séparés par des espaces pour une opération : $R1_{i}$, $R2_{i}$, $C1_{i}$, $C2_{i}$, $X_{i}$.
Sortie
- Lignes $1,\ldots,Q$ : sur la ligne $i+1$, affichez un entier, le nombre de cases concordantes après l’opération $i$.
Exemples
Entrée 1
17 15 10 111111101111111 111111000111111 111110000011111 111100000001111 111000000000111 111100000001111 111000000000111 110000000000011 111000000000111 110000000000011 100000000000001 110000000000011 100000000000001 000000000000000 111111000111111 111111000111111 111111000111111 5 8 2 14 1 8 17 3 7 1 4 5 10 15 0 7 16 12 14 1 2 17 13 14 0 2 6 2 3 1 13 14 4 8 1 3 6 6 7 1 1 16 10 11 0 7 16 10 10 0
Sortie 1
113 94 95 91 87 93 91 87 93 93
Remarque
Les vaches veulent peindre un arbre de fête.
Après la première opération, la grille est :
000000000000000 000000000000000 000000000000000 000000000000000 011111111111110 011111111111110 011111111111110 011111111111110 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000
113 cases correspondent à celles de l’image de l’arbre ; elles sont marquées 'x' ci-dessous (les autres bits sont leur valeur après le premier jet de peinture) :
0000000x0000000 000000xxx000000 00000xxxxx00000 0000xxxxxxx0000 0xx111111111xx0 0xxx1111111xxx0 0xx111111111xx0 0x11111111111x0 000xxxxxxxxx000 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 xxxxxxxxxxxxxxx 000000xxx000000 000000xxx000000 000000xxx000000
Auteurs du problème : Brian Hamrick et Neal Wu, 2008