Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

SUMMATRX - Sumowanie w macierzy

Dana jest macierz NxN.

Będziesz poproszony o przetworzenie następujących zapytań :

SET x y val

SUM x1 y1 x2 y2

Gdzie SET: ustawia komórkę x,y w macierzy na wartość val.

SUM: sumuje prostokąt w macierzy ograniczony lewym dolnym wierzchołkiem x1;y1 oraz górnym prawym wierzchołkiem x2;y2 tego prostokąta

Input

Pierwsza linia zawiera liczbę T, liczbę testów(T<=10)

Pierwsza linia każdego testu wejścia stanowi liczba N: wymiar macierzy. (N<1024)

Następnie w nieokreślonej liczbie linii jest podana komenda SUM, SET lub END.

Po poleceniu SET podane będą 3 wartości : x,y,val

Po poleceniu SUM podane będą 4 wartości : x1,y1,x2,y2

Komórki podawane w poleceniach są z przedziału <0;n)

Typ int wystarczy, aby wykonać wszystkie operacje.

Polecenie END odpowiada końcowi testu.

Output

Dla każdego polecenia SUM wypisz wynik oddzielając je znakiem nowej linii.

Example

Input:
1
4
SET 0 0 1
SUM 0 0 3 3
SET 2 2 12
SUM 2 2 2 2
SUM 2 2 3 3
SUM 0 0 2 2
END

Output:
1
12
12
13

Dodane przez:Krzysztof Lewko
Data dodania:2011-07-02
Limit czasu wykonania programu:0.211s-0.635s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU

ukryj komentarze
2014-12-31 14:19:55 Witold D³ugosz
Masz rację. Jest N<=1024.
2014-12-31 12:15:36 Pawe³ Kieliszczyk
Wydaje mi się, że testy nie spełniają specyfikacji wejścia, a konkretnie:
"Pierwsza linia każdego testu wejścia stanowi liczba N: wymiar macierzy. (N<1024)"

Ktoś potwierdzi?
2011-07-24 22:40:52 Krzysztof Lewko
Ja nie mam drzewa przedziałowego i chyba jeszcze 1 lub 2 osoby :) Inna struktura, ale napisz do mnie na forum PW to prześlę ci info o tej ciekawej strukturze, tutaj nei będę spojlować.
Patrzę bardzo martwisz się o fastI/O,
sam zakodź szybkie wczytywanie ( czyli znak po znaku i zapisujesz jako liczbę ), kilka linijek kodu :)

Ostatnio edytowany: 2011-07-24 22:42:52
2011-07-21 18:09:21 Maxardis
Mam pytanko do ludzi, którzy zrobili to zadanko.
Czy używacie jakiś przyspieszaczy IO? Czy po prostu mam dość kiepską implementacje drzewa przedziałowego?

I jeśli to to drugie(a na to stawiam) to czy mógłby ktoś miły podzielić się swoim źródłem na podstawie którego tworzył swoje drzewo.

A i jeszcze w jaki sposób zapisujecie to drzewo przedziałowe? Ja używam macierzy int[2050][2050] i zajmuje ona 2 razy więcej pamięci niż czołówce.

Ostatnio edytowany: 2011-07-21 19:13:37
2011-07-03 17:44:44 Krzysztof Lewko
Tak, zgadza się :) Początkowo w zadaniu nie było liczby testów, potem je dodałem, dlatego tak zostało. Już poprawione.
2011-07-03 17:35:59 Maxardis
Polecenie END oznacza chyba koniec testu a nie całego programu, tak mi sie przynajmniej wydaje
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.