Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2014-04-23 14:39:42.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:speculum.in, speculum.outSursăONIS 2014, Runda 4
AutorPaul DiacAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Speculum

Se considera urmatorul caroiaj infinit, cu liniile si coloanele numerotate incepand cu 1:

    1 2 3 4 ...
   ---------
1 | 1 1 1 1 ...
2 | 2 1 1 2
3 | 1 2 1 2 ...
4 | 2 2 1 1

Construit in felul urmator:

Se incepe de la patratul cu de latura 1 ce contine pe pozitia (1, 1) valoarea 1. La fiecare pas se dubleaza dimensiunea patratului in felul urmator:

1. Se completeaza in dreapta patratului curent un patrat de aceeleasi dimensiuni, care are coloanele cu aceeleasi valori ca si patratul initial, insa oglindite fata de dreapta verticala dintre aceste patrate. Mai exact daca primul patrat are coloanele C1, C2, ... , Cn-1, Cn patratul din dreapta lui va avea coloanele Cn, Cn-1, ... C2, C1.

2. Se completeaza in jos fata de patratul unitial un alt patrat de aceeleasi dimensiuni, iar valorile din acest patrat se obtin oglindind fata de orizontala liniile patratului initial si interschimband valorile 1 cu 2.

3. Se completeaza in dreapta - jos fata de patratul initial un nou patrat de aceeleasi dimensiuni care se obtine din patratul initial oglindind atat liniile (orizontal) cat si coloanele (vertical). Valorile raman neschimbate.

De exemplu la pasul al doilea avem patratul

1 1
2 1

si conform 1. adaugam in dreapta lui patratul

1 1
1 2 (acesta este patratul initial 'in oglinda', avand aceeleasi coloane dar in ordinea inversa),

si dedesupt:

1 2
2 2 (patratul initial oglindint 'orizonta', si cu valorile 1 si 2 interschimbate),

iar in dreapta - jos:

1 2
1 1 (patratul initial oglindit de doua ori, sau cel de la pasul 2 oglindit inca odata orizontal).

Pentru a rezolva problema trebuie sa raspundeti la cateva query-uri de forma (x1, y1, x2, y2), cu seminificatia: care este suma numerelor din caroiaj aflate in dreptunghiul cu colturile stanga-sus (x1, y1) si dreapta-jos (x2, y2)?

Date de intrare

Fisierul de intrare speculum.in contine pe prima linie numarul de query-uri T. Urmatoarele T linii contin cate 4 numere intregi : x1 y1 ×2 y2.

Date de ieşire

In fisierul de iesire speculum.out afisati pe cate o linie cate un singur numar, raspunsul la query-uri in ordinea din fisierul de intrare.

Restricţii

  • 1 ≤ T ≤ 20
  • 1 ≤ x1 ≤ x2 ≤ 109 si 1 ≤ y1 ≤ y2 ≤ 109

Exemplu

speculum.inspeculum.out
6
1 1 1 2
1 1 2 1
2 2 4 4
5 6 6 8
12 2 16 4
11512 62723 44722 85311
2
3
13
9
24
85619882

Explicaţie

Testul 4 cere suma patratului definit de colturile (5, 6) si (6, 8). Acesta are valorile:

1 2 2
1 2 1

de suma 9.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?