Die Kühe wollen ihre Festtagsstimmung durch ein Bild zeigen! Es ist ein $R$ $\times$ $C$ Raster $(1 \le R \le 50,000; 1 \le C \le 15)$ aus Einheitsquadraten, jedes0 oder1. Zeilen haben Nummern $1,\ldots,R$, Spalten $1,\ldots,C$.
Unter Zeitdruck bitten sie Nachbarn nördlich der Grenze um Hilfe. Unter freundlicher Aufsicht des Elchs Canmuu bauen sie eine Maschine, die ganze Farbeimer aufs Bild wirft! Anfangs ist alles0; die Maschine färbt ein Rechteck mit0 oder1. Canmuu schlägt $Q$ Operationen $(1 \le Q \le 10,000)$ vor; Operation $i$ besteht aus fünf ganzen Zahlen $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)$ und färbt alle Felder mit Zeilen zwischen $R1_{i}$ und $R2_{i}$ und Spalten zwischen $C1_{i}$ und $C2_{i}$, Grenzen eingeschlossen, mit $X_{i}$.
So passieren leicht Fehler. Canmuu bittet dich, nach jeder Operation die Anzahl der Einheitsquadrate mit richtiger Farbe zu bestimmen.
Speicherlimit:64 MB
Zeitlimit:1.5 Sekunden
Eingabe
- Zeile1: drei durch Leerzeichen getrennte ganze Zahlen $R$, $C$, $Q$.
- Zeilen $2,\ldots,R+1$: Zeile $i+1$ enthält $C$ Zeichen '0' oder '1', die Zeile $i$ darstellen.
- Zeilen $R+2,\ldots,R+Q+1$: Zeile $R+i+1$ enthält fünf durch Leerzeichen getrennte ganze Zahlen für eine Maloperation: $R1_{i}$, $R2_{i}$, $C1_{i}$, $C2_{i}$, $X_{i}$.
Ausgabe
- Zeilen $1,\ldots,Q$: Gib in Zeile $i+1$ eine ganze Zahl aus, die Anzahl passender Felder nach Operation $i$.
Beispiele
Eingabe 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
Ausgabe 1
113 94 95 91 87 93 91 87 93 93
Hinweis
Die Kühe möchten einen Festtagsbaum malen.
Nach der ersten Operation sieht das Raster so aus:
000000000000000 000000000000000 000000000000000 000000000000000 011111111111110 011111111111110 011111111111110 011111111111110 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000
113 Felder entsprechen dem zugehörigen Feld im Baumbild; sie sind unten mit 'x' markiert (die übrigen Bits zeigen den Zustand nach dem ersten Farbwurf):
0000000x0000000 000000xxx000000 00000xxxxx00000 0000xxxxxxx0000 0xx111111111xx0 0xxx1111111xxx0 0xx111111111xx0 0x11111111111x0 000xxxxxxxxx000 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 xxxxxxxxxxxxxxx 000000xxx000000 000000xxx000000 000000xxx000000
Aufgabenautoren: Brian Hamrick und Neal Wu, 2008