Cod sursa(job #2567953)

Utilizator alex23alexandru andronache alex23 Data 3 martie 2020 19:51:02
Problema Arbori de intervale Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.16 kb
#include <vector>
#include <iostream>

void update(std::vector<int>& tree, int position, int index, int value, int start, int end, const std::function<int(int, int)>& compare) {
    if ( start == end ) {
        tree[index] = value;
        return;
    }

    int div = (start + end) / 2;
    if (position <= div)
        update(tree, position, 2*index + 1, value, start, div, compare);
    else
        update(tree, position, 2*index + 2, value, div+1, end, compare);

    tree[index] = compare( tree[2*index + 1], tree[2*index+2] );
}

void query(std::vector<int>& tree, int index, int start, int finish, int left, int right, int& maxim, const std::function<int(int, int)>& compare) {
    if ((start <= left) && (right <= finish)) {
        maxim = compare(maxim, tree[index]);
        return;
    }

    int m = (left + right) / 2;
    if (start <= m) query(tree, 2 * index + 1, start, finish, left, m, maxim, compare);
    if (finish >= m + 1) query(tree, 2 * index + 2, start, finish, m + 1, right, maxim, compare);
}

int query(std::vector<int>& tree, int begin, int end, int size, const std::function<int(int, int)>& comp, int defaultValue) {
    int maxim = defaultValue;
    query(tree, 0, begin, end, 0, size, maxim, comp);
    return maxim;
}

void update(std::vector<int>& tree, int position, int value, int size, const std::function<int(int, int)>& compare) {
    update(tree, position, 0, value, 0, size, compare);
}

#ifndef TESTING
int main() {
    FILE *f = fopen("arbint.in", "r");
    FILE *g = fopen("arbint.out", "w");

    int N, M, x;
    long long n = 0;
    auto max = [](int x, int y) { return std::max(x, y); };
    fscanf(f, "%d %d", &N, &M);
    int j = 1;
    while (j < 2 * N) {
        n += j;
        j *= 2;
    }
    std::vector<int> a(n, 0);

    for (int i = 0; i < N; ++i) {
        fscanf(f, "%d", &x);
        update(a, i, x, N - 1, max);
    }

    for (int i = 0; i < M; ++i) {
        int x, y, z;
        fscanf(f, "%d %d %d", &x, &y, &z);
        if (x) {
            update(a, y - 1, z, N - 1, max);
        }
        else {
            fprintf(g, "%d\n", query(a, y - 1, z - 1, N - 1, max, 0));
        }
    }

    fclose(f);
    fclose(g);

    return 0;
}
#endif