Mai intai trebuie sa te autentifici.
Cod sursa(job #734364)
Utilizator | Data | 14 aprilie 2012 01:46:51 | |
---|---|---|---|
Problema | Arbori de intervale | Scor | 50 |
Compilator | fpc | Status | done |
Runda | Arhiva educationala | Marime | 2.03 kb |
Program P1;
var fi,fo : text;
i,n,m,k,sol,a,b : longword;
max : array[0..299999] of longword;
Function maxim(a,b:longword):longword;
begin
if a>b then maxim:=a
else maxim:=b;
end;
Procedure creare(left,right,nod : longword);
var mijl:longword;
begin
if left=right then read(fi,max[nod])
else begin
mijl:=(left+right) div 2;
creare(left,mijl,2*nod);
creare(mijl+1,right,2*nod+1);
max[nod]:=maxim(max[2*nod],max[2*nod+1]);
end;
end;
Procedure caut_max(left,right,nod:longword);
var mijl:longword;
begin
if (a<=left) and (b>=right) then begin
if sol<max[nod] then sol:=max[nod];
end
else
begin
mijl:=(left+right) div 2;
if a<=mijl then caut_max(left,mijl,2*nod);
if b>=mijl+1 then caut_max(mijl+1,right,2*nod+1);
end;
end;
Procedure update(left,right,nod:longword);
var mijl:longword;
begin
if left=right then max[nod]:=b
else begin
mijl:=(left+right) div 2;
if a<=mijl then update(left,mijl,2*nod)
else update(mijl+1,right,2*nod+1);
max[nod]:=maxim(max[2*nod],max[2*nod+1]);
end;
end;
begin
assign(fi,'arbint.in'); reset(fi); readln(fi,n,m);
assign(fo,'arbint.out'); rewrite(fo);
creare(1,n,1);
for i:=1 to m do begin
readln(fi,k,a,b);
if k=0 then begin
sol:=0;
caut_max(1,n,1);
writeln(fo,sol);
end
else update(1,n,1);
end;
close(fi); close(fo);
end.