Cod sursa(job #1097756)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 3 februarie 2014 21:49:06
Problema Arbori de intervale Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<fstream>
using namespace std;
int aint[400001],i,n,op,x,y,sol,m;

void update(int nod, int l, int r) {
     if (l==r) aint[nod]=x;
     else {
          int mid=(l+r)/2;
          if (y<=mid) update(2*nod,l,mid); else update(2*nod+1,mid+1,r);
          aint[nod]=max(aint[2*nod],aint[2*nod+1]);
          }
}

void query(int nod, int l, int r) {
     if (l>=x&&r<=y) sol=max(sol,aint[nod]);
      else {
           int mid=(l+r)/2;
           if (x<=mid) query(2*nod,l,mid);
           if (y>mid) query(2*nod+1,mid+1,r);
           }
}

int main(void) {
    ifstream fin("arbint.in");
    ofstream fout("arbint.out");
    
    fin>>n>>m;
    for (i=1; i<=n; ++i) { fin>>x; y=i; update(1,1,n); }
    
    for (i=1; i<=m; ++i) {
         fin>>op>>x>>y;
         if (op==0) {
                     sol=0;
                     query(1,1,n);
                     fout<<sol<<"\n";
                     }
         else { swap(x,y); update(1,1,n); }
         }
  return(0);
}