Cod sursa(job #348542)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 16 septembrie 2009 00:04:01
Problema Arbori de intervale Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>

using namespace std;

#define fin  "arbint.in"
#define fout "arbint.out"

#define NMAX 100000

int N, M, arb[4 * NMAX];
int stTarget, drTarget, ret, value;

inline int maxf(int a, int b) { return ( a < b ) ? (b) : (a); }

void insert(int nod, int st, int dr)
{
	if ( st == dr )
	{
		arb[ nod ] = value;
		return ;
	}

	int mid = st + (dr - st)/2;

	if ( stTarget <= mid )
		insert(2*nod,st,mid);
	else
		insert(2*nod + 1,mid + 1, dr);

	arb[nod] = maxf(arb[2*nod],arb[2*nod+1]);
}

void query(int nod, int st, int dr)
{
	if ( stTarget <= st && dr <= drTarget )
	{
		ret = maxf(ret,arb[nod]);
		return ;
	}

	int mid = st + (dr-st)/2;

	if ( stTarget <= mid )
		query(2*nod,st,mid);
	if ( drTarget > mid )
		query(2*nod+1,mid + 1,dr);
}

int main()
{
	int i, val, a, b, op;

	ifstream f1(fin);
	ofstream f2(fout);

	f1 >> N >> M;

	for ( i = 1; i <= N; ++i )
	{
		stTarget = i;
		f1 >> value, insert(1,1,N);
	}

	for ( i = 1; i <= M; ++i )
	{
		f1 >> op >> a >> b;
		if ( !op )
		{
			ret = 0;
			stTarget = a;
			drTarget = b;
			query(1,1,N);
			f2 << ret << endl;
		}
		else
		{
			value = b;
			stTarget = a;
			insert(1,1,N);
		}
	}

	return 0;
}