Cod sursa(job #2107899)

Utilizator calin9819Costea Calin calin9819 Data 17 ianuarie 2018 19:41:38
Problema Arbori de intervale Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f("arbint.in");
ofstream g("arbint.out");

int N, M, arbore[450000], r;

void adaug(int nod, int st, int dr, int x, int i) {
    if (st == dr) {
        arbore[nod] = x;
        return;
    }

    int mijloc = (st + dr)/2;
    if (i <= mijloc) adaug(2 * nod, st, mijloc, x, i);
    else adaug(2 * nod + 1, mijloc + 1, dr, x, i);
    arbore[nod] = max(arbore[2 * nod], arbore[2 * nod + 1] );
}


void query(int nod, int st, int dr, int a, int b)
{
     if (a <= st && dr <= b)
     {
          if (r < arbore[nod]) r = arbore[nod];
          return;
     }

     int mijloc = (st + dr)/2;
     if (a <= mijloc) query(2 * nod, st, mijloc, a, b);
     if (mijloc < b) query(2 * nod + 1, mijloc + 1, dr, a, b);
}

int main()
{
    f >> N >> M;
    for (int i = 1; i <= N; i++) {
        int x;
        f >> x;
        adaug(1, 1, N, x, i);
    }

    for (int i = 1; i <= M; i++) {
        int tip, a, b;
        f >> tip >> a >> b;
        if (tip == 1) adaug(1, 1, N, b, a);
        else {
            r = 0;
            query(1, 1, N, a, b);
            g << r << '\n';
        }
    }
    return 0;
}