Cod sursa(job #2763649)

Utilizator GligarEsterabadeyan Hadi Gligar Data 15 iulie 2021 18:14:21
Problema Arbori de intervale Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>

using namespace std;

ifstream fin("arbint.in");
ofstream fout("arbint.out");

const int nmax=100000, n2max=(1<<17);

int v[2*n2max];

int max(int x,int y){
    if(x>y){
        return x;
    }else{
        return y;
    }
}

int solutie(int a,int b, int nod, int l, int r){
    if(a>r||b<l){
        return -1;
    }else if(a<=l&&r<=b){
        return v[nod];
    }else{
        int x=solutie(a, b, nod*2, l, (l+r)/2);
        int y=solutie(a, b, nod*2+1, (l+r)/2+1, r);
        return max(x,y);
    }
}

int main(){
    int n,m;
    fin>>n>>m;
    int n2=1;
    while(n2<n){
        n2*=2;
    }
    for(int i=1;i<=n;i++){
        fin>>v[n2+i-1];
    }
    for(int i=n+1;i<=n2;i++){
        v[n2+i-1]=-1;
    }
    for(int i=n2-1;i>=1;i--){
        v[i]=max(v[i*2],v[i*2+1]);
    }
    for(int i=1;i<=m;i++){
        int k,a,b;
        fin>>k>>a>>b;
        if(k==1){
            v[n2+a-1]=b;
            for(int x=(n2+a-1)/2;x>0;x/=2){
                v[x]=max(v[x*2],v[x*2+1]);
            }
        }else{
            fout<<solutie(a,b,1,1,n2)<<"\n";
        }
    }
    return 0;
}