ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1126. Magnetic Storms

Help,.. I have WA2...
Posted by Neo Nomaly 27 Jan 2006 16:35
type
  ch=record
       x,i:longint;
     end;
const
  maxn=25000;
var
  a,heap:array[1..maxn] of ch;
  n,m,lh:longint;
procedure init;
var
  x:longint;
begin
  readln(m);
  n:=0;
  while true do begin
    readln(x);
    if x=-1 then break;
    inc(n);
    a[n].x:=x;
  end;
  lh:=0;
end;
procedure swap(var x,y:ch);
var
  xx:ch;
  b:longint;
begin
  xx:=x;
  x:=y;
  y:=xx;
  b:=a[y.i].i;
  a[y.i].i:=a[x.i].i;
  a[x.i].i:=b;
end;
procedure up(x:longint);
begin
  while (x>1) and (heap[x div 2].x<heap[x].x) do begin
    swap(heap[x div 2],heap[x]);
    a[heap[x].i].i:=x;
    a[heap[x div 2].i].i:=x div 2;
    x:=x div 2;
  end;
  a[heap[x].i].i:=x;
end;
procedure insert(x,i:longint);
begin
  inc(lh);
  heap[lh].x:=x;
  heap[lh].i:=i;
  up(lh);
end;
procedure down(x:longint);
begin
  while (x*2<=lh) and (x*2+1<=lh) do begin
    if (heap[x*2].x>heap[x].x) or (heap[x*2+1].x>heap[x].x) then begin
      if heap[x*2].x<heap[x*2+1].x then begin
        swap(heap[x*2+1],heap[x]);
        a[heap[x].i].i:=x;
        a[heap[x*2+1].i].i:=x*2+1;
        x:=x*2+1;
      end else begin
        swap(heap[x*2],heap[x]);
        a[heap[x].i].i:=x;
        a[heap[x*2].i].i:=x*2;
        x:=x*2;
      end;
    end else
      break;
  end;
  if x*2<=lh then begin
    if heap[x*2].x>heap[x].x then begin
      swap(heap[x*2],heap[x]);
      a[heap[x].i].i:=x;
      a[heap[x*2].i].i:=x*2;
      x:=x*2;
    end;
  end;
  a[heap[x].i].i:=x;
end;
procedure delete(x:longint);
begin
  swap(heap[x],heap[lh]);
  a[heap[lh].i].i:=0;
  heap[lh].i:=0;
  dec(lh);
  if x<lh then down(x);
end;
procedure solve;
var
  i:longint;
begin
  if n>=3 then begin
    for i:=1 to m do
      insert(a[i].x,i);
    writeln(heap[1].x);
    for i:=1 to n-m do begin
      delete(a[i].i);
      insert(a[i+m].x,i+m);
      writeln(heap[1].x);
    end;
  end;
end;
begin
  init;
  solve;
end.
Re: Help,.. I have WA2...
Posted by +FAMAS+ 28 Jan 2006 23:41
test
2
3
2
-1 :) answer 3