Cod sursa(job #1218728)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 12 august 2014 13:37:23
Problema Arbori de intervale Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <cstdio>
#include <algorithm>

#define DIM 666013
#define Nmax ((1 << 18) + 666)

using namespace std;
char buffer[DIM];
int poz = DIM - 1;

void read(int &A)
{
    A = 0;
    while('0' > buffer[poz] || buffer[poz] > '9')
        if(++poz == DIM) fread(buffer,1,DIM,stdin),poz = 0;
    while('0' <= buffer[poz] && buffer[poz] <= '9')
    {
        A = A * 10 + buffer[poz] - 48;
        if(++poz == DIM) fread(buffer,1,DIM,stdin),poz = 0;
    }
}
int A,B,pos,_newX,answer;

class SegmentTree{
private:
    int range[Nmax];
public:
    void Build(int li,int lf,int pz)
    {
        if(li == lf)
        {
            read(range[pz]);
            return;
        }
        int m = li + ((lf - li) >> 1);
        Build(li,m,pz<<1);
        Build(m+1,lf,(pz<<1)|1);
        range[pz] = max(range[pz<<1], range[(pz<<1)|1]);
    }
    void Update(int li,int lf,int pz)
    {
        if(li == lf)
        {
            range[pz] = _newX;
            return;
        }
        int m = li + ((lf - li) >> 1);

        if(pos <= m) Update(li,m,pz<<1);
        else Update(m+1,lf,(pz<<1)|1);

        range[pz] = max(range[pz<<1], range[(pz<<1)|1]);
    }
    void Querry(int li,int lf,int pz)
    {
        if(A <= li && lf <= B)
        {
            answer = max(answer,range[pz]);
            return;
        }
        int m = li + ((lf - li) >> 1);
        if(A <= m)  Querry(li,m,pz<<1);
        if(B > m) Querry(m+1,lf,(pz<<1)|1);
    }
}Aint;

int main()
{
    freopen("arbint.in","r",stdin);
    freopen("arbint.out","w" ,stdout);

    int N,Q,op,a,b;
    read(N);
    read(Q);
    Aint.Build(1,N,1);
    for(int i = 1; i <= Q; ++i)
    {
        read(op);
        read(a);
        read(b);
        if(op == 0){
            answer = 0;
            A = a;
            B = b;
            Aint.Querry(1,N,1);
            printf("%d\n",answer);
        }
        else
        {
            _newX = b;
            pos = a;
            Aint.Update(1,N,1);
        }
    }

    return 0;
}