Cod sursa(job #1972064)

Utilizator Robert29FMI Tilica Robert Robert29 Data 21 aprilie 2017 17:51:39
Problema Arbori de intervale Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include<stdio.h>
#define N 100001
FILE*f = fopen("arbint.in", "r");
FILE*g = fopen("arbint.out", "w");

int v[4 * N];

int max(int a, int b)
{
    return a > b ? a : b;
}

void Update(int position, int value, int left, int right, int vertice)
{
	if(left == right)
	{
		v[vertice] = value;
		return;
	}

	int leftVertice = vertice * 2;
	int rightVertice = leftVertice + 1;
	int mid = (left + right) / 2;

	if(position <= mid)
	{
		Update(position, value, left, mid, leftVertice);
	}
	else
	{
		Update(position, value, mid + 1, right, rightVertice);
	}
	v[vertice] = max(v[leftVertice], v[rightVertice]);
}

int Query(int start, int end, int left, int right, int vertice)
{
	if(start <= left && right <= end)
	{
		return v[vertice];
	}

	int leftVertice = vertice * 2;
	int rightVertice = leftVertice + 1;
	int mid = (left + right) / 2;


    int result = 0;
	if(mid >= start)
	{
		result = max(result, Query(start, end, left, mid, leftVertice));
	}

	if(mid < end)
	{
		result = max(result, Query(start, end, mid + 1, right, rightVertice));
	}

	return result;
}


int main(){
	int n, m;
	fscanf(f, "%d%d", &n, &m);

	for(int i = 1; i <= n; ++i)
	{
		int x;
		fscanf(f, "%d", &x);
		Update(i, x, 1, n, 1);
	}

	for(int i = 1; i <= m; ++i)
	{
		int op;
		fscanf(f, "%d", &op);
		if(!op)
		{
			int start, end;
			fscanf(f, "%d%d", &start, &end);
			fprintf(g, "%d \n", Query(start, end, 1, n, 1));
		}
		else
		{
			int position, value;
			fscanf(f, "%d%d", &position, &value);
			Update(position, value, 1, n, 1);
		}
	}


	fclose(f);
	fclose(g);
	return 0;
}