Tävlingsprogrammering/Uppgifter/Smutsig tvätt

Smutsig tvätt

Efter att ha tvättat lakan brukar jag hänga dem på tork utanför huset. Tyvärr så har starka vindar gjort att torkstället gått sönder, så jag har varit tvungen att lägga ut dem på gräsmattan istället.

Gräsmattan kan ses som ett oändligt stort rutnät, där varje ruta representeras av ett koordinatpar. Lakanen ligger utplacerade i rutnätet med sidorna parallella med koordinataxlarna. Ett lakan kan helt eller delvis överlappa andra lakan.

Mitt på gräsmattan, (0,0), finns ett brunnslock. Tyvärr har jag sån otur att något strul med avloppet har uppstått och smutsvatten har börjat läcka upp ur brunnen och ut på gräsmattan där jag lagt mina lakan. Vi antar att smutsvattnet sprider sig med en jämn hastighet från brunnen. Vid tidpunkt 0 så är enbart ruta (0,0) fylld med smutsvatten. Därefter sprider sig vattnet en ruta per sekund i alla åtta riktningar, enligt figuren nedan. De rutor vattnet når fläckar ner samtliga lakan som ligger i den rutan.

Gräsmattan i det första exemplet efter noll, en respektive två sekunder. Skriv ett program som, givet M punkter i tiden, beräknar den totala arean av lakan som är smutsiga för varje tidpunkt.

Indata

Den första raden innehåller ett heltal N (1 ≤ N ≤ 100 000), antalet lakan.

Sedan följer N rader innehållande fyra heltal, x1, y1, x2 och y2 (-1 000 000 ≤ x1 ≤ x2 ≤ 1 000 000, -1 000 000 ≤ y1 ≤ y2 ≤ 1 000 000). Dessa koordinater representerar diagonalt motsatta hörn för ett lakan (notera återigen att koordinaterna representerar rutor i rutnätet, inte punkter i planet). Inget lakan kommer täcka ruta (0,0).

Därefter följer en rad innehållande heltalet M (1 ≤ M ≤ 100 000), antalet punkter i tiden.

Sedan följer M rader innehållande heltal mellan 0 och 1 000 000 som motsvarar tidpunkterna. Dessa kommer att ges i strikt stigande ordning.

Utdata

För varje tidpunkt, skriv ut en rad innehållande den total arean av smutsiga lakan, i samma ordning som tidpunkterna anges.

Bedömning

I testfall värt 20% av totalpoängen gäller 1 ≤ M, N ≤ 1000.

Exempel 1: Indata

Exempel 1: Utdata

5
15

Exempel 2: Indata

4
5 1 8 4
-8 1 -5 4
-10 2 10 3
6 0 8 10
6
1 2 3 4 7 9

Exempel 2: Utdata

Exempel 3: Indata

1
1 1 1000000 1000000
3
100 10000 1000000

Exempel 3: Utdata

10000
100000000
1000000000000

Exempel 4: Indata

8
0 1 0 1
2 0 2 0
0 -3 0 -3
-4 0 -4 0
0 5 1 5
-1 6 0 6
-7 0 -7 1
-8 -1 -8 0
10
1 2 3 4 5 6 7 8 9 10

Exempel 4: Utdata

Lösning

Det triviala vore ju att för varje tidpunkt som ska skrivas ut, kolla för varje lakan hur stor area som täcks. Men om vi har 10^5 lakan och 10^5 tidpunkter blir det totalt 10^10 tester. Det är alldeles för segt. Vi kan inte heller försöka rita upp rutnätet som en array i två dimensioner, eftersom det kommer att kräva för mycket minne. Det enda möjliga sättet som återstår är att på något sätt för varje tidpunkt snabbt ta reda på hur många extra rutor som kommer vara täckta när nästa tidpunkt inträffar. En sådan algoritm kommer att gå på linjär tid. Och det går!

När vatten kommer in över ett lakan, kan det komma in på lite olika sätt. Det kan t.ex. komma in så att en sida av lakanet direkt fylls av vatten, så nästföljande tider kommer en konstant mängd vatten in för varje tidsenhet. För sådana lakan kan vi helt enkelt skapa en array med en miljon element, dvs. ett per tidsenhet, som registrerar ökningstakten/acceleration/andraderivata/whatever. Till en början innehåller den 0 på alla element. Om ett lakan börjar få in vatten i tidsenheten 5 och vattnet kommer gå utanför lakanet i tidsenheten 10, och mängden vatten som kommer in för varje tidsenhet är 6 (dvs. bredden på lakanet är 6 och höjden är 10-5=5), då kan vi i arr[5] addera 6, och i arr[10] subtrahera 6. Eftersom vi använder samma array för alla element behöver vi inte gå igenom samtliga lakan för samtliga tidsenheter. Vi kan istället bara loopa igenom alla tidsenheter, alltså från 1 till 10^6 och ha en variabel "area täckt" och "area extra per tidsenhet". Den senare variabeln justeras för varje tidsenhet vi loopar över, och justeringen hämtas från vår array.

Det finns också kvadratiska lakan som är utlagda så att när vatten kommer in för första gången blir enbart en enda hörnruta fylld. För varje extra tidsenhet kommer den fyllas på "diagonalt". Först kommer en kvadrat med sidan 1 vara fylld i nedre hörnet, sedan kommer en kvadrat med sidan 2 vara fylld i nedre hörnet, sedan en kvadrat med sidan 3 i nedre hörnet osv. Dvs. först är ökningen 1, sedan 3, 5, 7, 9 osv. Om vi i en viss tidpunkt har fyra sådana lakan som är halvtäckta, kommer alltså aktuella ökningen öka med 2*4 för varje tidsenhet (ökningstakt/acceleration/andraderivata/whatever). Vi behöver lite fler arrayer för denna sorts lakan. Vi behöver hålla koll på hur många nya sådana lakan startar i en viss tidpunkt, och hur många lakan som slutar i en viss tidspunkt. När vi sedan loopar igenom alla tidsenheter och går igenom allt behöver vi då variabler för "aktuell ökning" och "hur många sådana lakan vi är inne i". När ett lakan avslutas (dvs. när det är helt fyllt) måste vi också minska aktuella ökningen med avseende på dess storlek. Vi kan skapa en array för hur mycket vi måste minska aktuella öknings-variabeln när vi avslutar lakan, för varje tidsenhet. Så om vi avslutar två kvadrater i en viss tidsenhet, en storlek 3x3, och en 5x5, skulle nästa aktuella ökning bli 9 och 13. Vi sparar då 9+13 till denna array för denna tidsenhet.

Hur gör vi för lakan som inte uppfyller ovanstående villkor? Enkelt! Det går alltid att klippa sönder lakan (dvs. dela upp) så att man får kvar bitar som är på formen ovan. Det är egentligen inte så knepigt, men kan bli ganska slafsigt att skriva ...

När vi har läst in alla lakan och fyllt i alla arrayer börjar vi loopa igenom varje tidsenhet och beräkna förändringen, och lägga till till aktuell area. Om tidpunkten var en sådan som skulle skrivas ut så skriver vi ut svaret. Glöm inte att skriva ut 0 då T=0 ;) (även om nu det fallet inte fanns i testdatan...)

Tänk även på att använda 64-bitars heltal, eftersom 32-bit inte räcker.