Mai intai trebuie sa te autentifici.
Cod sursa(job #898309)
Utilizator | Data | 28 februarie 2013 09:52:43 | |
---|---|---|---|
Problema | Arbori de intervale | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.5 kb |
#include <cstring>
#include <cstdio>
#include <cmath>
int * array[18];
int size[18];
void change(int i, int v) {
array[0][i] = v;
for (int k = 1; k < 18; ++k) {
i = i / 2;
int a = array[k - 1][i * 2 + 0];
int b = array[k - 1][i * 2 + 1];
array[k][i] = a > b ? a : b;
}
}
int max(int a, int b) {
return(a > b ? a : b);
}
int maxim(int k, int l, int r) {
if (l == r) {
return(array[k][l]);
}
if (l % 2) {
return(max(array[k][l], maxim(k, l + 1, r)));
} else {
if (r % 2) {
return(maxim(k + 1, l / 2, r / 2));
} else {
return(max(array[k][r], maxim(k, l, r - 1)));
}
}
}
int main() {
FILE * in = fopen("arbint.in", "rt");
FILE * out = fopen("arbint.out", "wt");
size[0] = 1 << 17;
for (int k = 1; k < 18; ++k) {
size[k] = size[k - 1] / 2 + size[k - 1] % 2;
}
for (int k = 0; k < 18; ++k) {
array[k] = new int[size[k]];
}
int n, m;
fscanf(in, "%d%d", &n, &m);
for (int i = 0; i < n; ++i) {
fscanf(in, "%d", &array[0][i]);
}
int size = n;
for (int k = 1; k < 18; ++k) {
size = size / 2 + size % 2;
for (int i = 0; i < size; ++i) {
int a = array[k - 1][i * 2 + 0];
int b = array[k - 1][i * 2 + 1];
array[k][i] = a > b ? a : b;
}
if (size % 2) {
array[k][size] = 0;
}
}
for (int i = 0; i < n; ++i) {
int t, x, y;
fscanf(in, "%d%d%d", &t, &x, &y);
if (t) {
change(x - 1, y);
} else {
fprintf(out, "%d\n", maxim(0, x - 1, y - 1));
}
}
fclose(in);
fclose(out);
}