Cod sursa(job #2245849)

Utilizator pinteastefanPintea Teodor Stefan pinteastefan Data 25 septembrie 2018 23:37:19
Problema Arbori de intervale Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;
int val[4 * maxn];
int noduri[4 * maxn];
int n, m, a, b, raspuns, op;

void update (int nod, int stanga, int dreapta, int pozitie, int valoare){
    if (stanga > pozitie || dreapta < pozitie ){
        return;
    }
    if (stanga == dreapta){
        val[nod] = valoare;
        return;
    }
        update(nod * 2, stanga, (stanga + dreapta)/ 2, pozitie, valoare);
        update(nod * 2 + 1, (stanga + dreapta)/ 2 + 1, dreapta, pozitie, valoare);
        val[nod] = max(val[2 * nod], val[2 * nod + 1]);
}

void query (int nod, int stanga, int dreapta){
    if (stanga >= a  && dreapta <= b){
        raspuns = max(raspuns, val[nod]);
        return;
    }
    int mijloc = (stanga + dreapta)/ 2;
    if (mijloc >= a){
        query(nod * 2, stanga, mijloc);
    }
    if (mijloc < b){
        query(nod * 2 + 1, mijloc + 1, dreapta);
    }
}

int main() {
    ifstream f("arbint.in");
    ofstream g("arbint.out");
    f >> n >> m;
    for (int i = 1; i <= n; i++){
        f >> noduri[i];
        update(1, 1, n , i, noduri[i]);
    }
    for (int i = 1; i <= m; i ++){
        f >> op >> a >> b;
        if ( op == 0){
            raspuns = 0;
            query(1, 1, n);
            g << raspuns << "\n";
        }
        else{
            update( 1, 1, n , a , b);
        }
    }
    return 0;
}