Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
FR_01_06 - Ruchy tektoniczne |
Profesor Algobit w wolnych chwilach (np. na wakacjach) zajmuje się geologią. Tym razem bada tereny podatne na ruchy tektoniczne. Interesuje go, jak często zmienia się różnica między najwyższym a najniższym punktem na pewnym obszarze. Dla uproszczenia, nie bada całego obszaru, tylko obszar w zdłuż pewnej prostej, na której oznaczył sobie czujniki oddalone od siebie o pewną jednostkę. Profesor czasami potrzebuje tylko wyniku dla pewnego ograniczonego przedziału. Niestety na wakacjach zepsuł mu się komputer i poprosił Ciebie o napisanie programu, który zautomatyzuje obliczenia profesora.
Wejście
W pierwszym wierszu jedna liczba n określająca liczbę czujników (numerację zacznamy od 1), gdzie n należy do przedziału [1..106].
W drugim wierszu n liczb całkowitych należących do przedziału [-107.. 107], określających wysokość danego czujnika nad poziomem morza.
Następnie jedna liczba q będąca liczbą zaptyań (q ≤ 107).
Każde zapytanie składa się z liczby o, która należy do zbioru: {0, 1}. Jeśli o ma wartość 0, to podane są jeszcze dwie liczby a i b, gdzie 1≤ a ≤ b ≤ n, to zapytanie o różnicę poziomów między początkiem w a i końcem w b, natomiast, jeśli o ma wartość 1, to podane są trzy liczby a, b oraz v, oznaczające, że w przedziale [a..b], czujniki zanotowały zmianę o v jednostek nad poziomem morza (1≤ a ≤ b ≤ n oraz v należy do przedziału [-107.. 107]).
Wyjście
Dla każdego o mającego wartość 0 należy wypisać maksymalną różnicę poziomów w przedziale [a..b].
Przykład
Wejście: 5 1 3 2 1 8 5 1 1 3 2 0 1 5 0 1 3 1 4 5 -3 0 1 5 Wyjście: 7 2 7
Dodane przez: | Marcin Kasprowicz |
Data dodania: | 2014-03-26 |
Limit czasu wykonania programu: | 1s-3s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |
Pochodzenie: | FRAKTAL |