Segment tree can help solve the problem. I've got AC 0.046s 512Kb.
My steps:
1. Read all input and build segment tree
2. Get rmq(i, i + m - 1) for all needed i

Here my solution. In c[x] I store how much I have elements with key x in set. So it is in this range M ≤ N ≤ 25000. But when I set size of c to 25000 I have got Crash on 4 test. What is wrong in my solution?
#include <stdio.h>
#include <vector>
#include <set>
#include <stdlib.h>
#include <algorithm>


int main(){
    /*freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);*/
    int m,b,c[200000],l,r,d;
    std::vector <int> a;
    std::set <int> set;
    std::set <int>::iterator it;
    memset(c,0,sizeof(c));
    scanf("%d",&m);
    scanf("%d",&b);
    while (b!=-1){
        a.push_back(b);
        scanf("%d",&b);
    }
    d=a.size();
    for (int i=0; i<std::min(m,d); i++){
        set.insert(a[i]);
        c[a[i]]++;
    }
    if (m-1<d && m!=0){
        l=0; r=m-1;
        while (r<d-1){
            it=set.end();
            it--;
            printf("%d\n",*it);
            r++;
            c[a[r]]++;
            set.insert(a[r]);
            c[a[l]]--;
            if (c[a[l]]==0) set.erase(a[l]);
            l++;
        }
    }
    if (set.size()>0){
        it=set.end();
        it--;
        printf("%d\n",*it);
    }else{printf("0");}
//    fclose(stdin); fclose(stdout);
}

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int izv[100001];
int main(){
int m;
cin>>m;
priority_queue<int>k;
vector<int>x;
int a,br=0;
while(1)
{
cin>>a;
if(a==-1)break;
x.push_back(a);
k.push(a);
br++;
if(br==m)cout<<k.top()<<endl;
else
if(br>m)
{
izv[x[0]]++;
x.erase(x.begin());
while(izv[k.top()]){izv[k.top()]--;k.pop();}
cout<<k.top()<<endl;
}
}

system("pause");
return 0;
}

    i use red black tree at first, but always get Crash (access violation) in test 4.then i change my method,using hash and get AC in 0.5s.but i still can not understand why i get crash in previous method. i guess there is something wrong with my red black tree. can anybody give the data of test 4 ? i just want to find out what's wrong with my red black tree.
    thanks!      please mail endlesscount@163.com

Edited by author 18.07.2011 11:33

var
  a:array[0..14000] of longint;
  b:array[-1..200000] of longint;
  n,i,j,k,max:longint;

begin
  read(n);
  fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);    b[-
1]:=10000;max:=-1;
  for i:=0 to n-2 do begin
    read(a[i]);
    if a[i]=-1 then begin writeln(max);halt;end;
    inc(b[a[i]]);
    if a[i]>max then max:=a[i];
  end;
  read(j);
  while j>=0 do begin
    inc(i);
    i:=i mod n;
    dec(b[a[i]]);a[i]:=j;
    inc(b[j]);
    if j>max then max:=j;
    while b[max]<=0 do dec(max);
    writeln(max);
    read(j);
  end;
end.

1229600
17:52:56 3 Jul 2006
wangyin
1126
Pascal
Accepted
0.5
330 KB
Funny......

#include <iostream>
using namespace std;
 int a[30000];
  int m,answer,k=0;
  int ans(int x){
      int amax=0;
      for(int i=x;i<x+m;i++)
        if (amax<a[i]) amax=a[i];

        return amax;
 }
 int main(){
 int n=0,N;
 cin>>m;
 for(int i=0;i<30000;i++){
 cin>>n;
 if (n==-1)break;
 else {a[i]=n; N=i;}
 }
 for(int i=0;i<=N-m+1;i++)
 cout<<ans(i)<<endl;
  return 0;
 }

bruteforce solution has ac. i think you should add some hard tests

I don't understand, why crash(access violation) in test1 ??!!

uses math;
var
n,k,l,m,d,a,i,j:longint;
p:array[0..66000] of longint;

begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
readln(m);
n:=0;
repeat
 inc(n);
 read(p[n]);
until p[n]=-1;
dec(n);

k:=1; d:=n;

while 1 shl k<n do inc(k);

n:=1 shl k;

for l:=d+1 to n do
p[l]:=-1;


for k:=n downto 1 do
begin
p[k+n-1]:=p[k];
end;

for k:=n-1 downto 1 do
begin
p[k]:=max(p[k*2],p[k*2+1]);
end;

for k:=0 to d-m do
begin
i:=k+n; j:=k+m-1+n;
a:=-1;

while i<j do
begin
 if odd(i) then begin a:=max(a,p[i]); inc(i); end;
 if not odd(j) then begin a:=max(a,p[j]); dec(j); end;
 i:=i div 2; j:=j div 2;
end;
a:=max(a,p[i]);

writeln(a);
end;

end.



I use {$R+} on Delphi, FP, TP - nothing Crash.

Edited by author 08.10.2009 11:30

New tests were added. Some authors lost AC after rejudge.

This is my solution:


var
  a:array[0..14000]of longint;
  b:array[0..100000]of longint;
  n,i,j,k,max:longint;
begin
  readln(n);
  b[0]:=1;max:=0;
  for i:=0 to n-2 do
    begin
      readln(a[i]);
      if a[i]=-1 then begin writeln(max);halt;end;
      inc(b[a[i]]);
      if a[i]>max then max:=a[i];
    end;
  readln(j);
  while j<>-1 do
    begin
      inc(i);
      i:=i mod n;
      dec(b[a[i]]);
      a[i]:=j;
      inc(b[j]);
      if j>max then max:=j;
      k:=max;
      if b[max]=0 then
        for max:=k-1 downto 0 do
          if b[max]>0 then break;
      writeln(max);
      readln(j);
    end;
end.


Can you help me???

program u1126;

var
  a:array[1..25000] of longint;
  n,max,i,j:longint;

begin
  readln(n); max:=-maxlongint;
  for i:=1 to n do
    begin
      readln(a[i]);
      if (a[i]=-1) and (i=1)
        then halt;
      if (a[i]=-1)
        then begin writeln(max); halt; end;
      if a[i]>max
        then max:=a[i];
    end;
  writeln(max);
  if max=a[1]
    then max:=a[2];
  i:=n+1;
  while true do
    begin
      readln(a[i]);
      if a[i]=-1
        then break;
      if a[i]>max
        then max:=a[i];
      writeln(max);
      if max=a[i-n+1]
        then max:=a[i-n+2];
      inc(i);
    end;
end.





I really can't find out where it wrongs!!

why WA #17?
who can help me....


type node=record
           dat,num:longint;
          end;

var a:array[1..30000]of node;
    s:array[1..30000]of longint;
    m:longint;
    i,j,t,k:longint;

procedure heap1(x,y:longint);
 var i,j:longint;
     k:node;
 begin
  i:=x;j:=i*2;k:=a[x];
  while j<=y do
   begin
    if (a[j+1].dat>a[j].dat)and(j<y) then inc(j);
    if k.dat>=a[j].dat then j:=y+1
    else begin
          a[i]:=a[j];s[a[j].num]:=i;
          i:=j;j:=i*2;
         end;
   end;
  a[i]:=k;s[k.num]:=i;
 end;

procedure heap2(x,y:longint);
 var i,j:longint;
     k:node;
 begin
  i:=y;j:=y shr 1;
  k:=a[y];
  while j>=1 do
   if a[j].dat>=k.dat then j:=0
   else begin
         a[i]:=a[j];s[a[j].num]:=i;
         i:=j;j:=j shr 1;
        end;
  a[i]:=k;s[k.num]:=i;
 end;

begin

 readln(m);
 for i:=1 to m do
  begin
   readln(a[i].dat);
   s[i]:=i;
   a[i].num:=i;
  end;
 for i:=m shr 1 downto 1 do
  heap1(i,m);
 writeln(a[1].dat);
 t:=m+1;
 readln(k);
 while k<>-1 do
  begin
   s[a[m].num]:=s[t-m];
   a[s[t-m]]:=a[m];
   heap1(1,m-1);
   a[m].dat:=k;
   a[m].num:=t;
   s[t]:=m;
   heap2(1,m);
   writeln(a[1].dat);
   inc(t);
   readln(k);
  end;
end.

I know test, where my prog works more then 3 sec, but there I get AC with time 0.015 sec...

I used the heapsort,but wa.HELP!

program ural1126(input,output);
var
  n,m,i,j,k:longint;
  id,num:array[1..35000] of longint;
  f,g:array[1..15000] of longint;
procedure swap(a,b:longint);
var
  x:longint;
begin
    x:=f[a];f[a]:=f[b];f[b]:=x;
    x:=id[g[a]];id[g[a]]:=id[g[b]];id[g[b]]:=x;
    x:=g[a];g[a]:=g[b];g[b]:=x;
end;

procedure sift(v,m:longint);
var
  maxi,l,r:longint;
begin
  l:=v*2;r:=l+1;maxi:=v;
  if (l<=m) and (f[l]>f[maxi]) then maxi:=l;
  if (r<=m) and (f[r]>f[maxi]) then maxi:=r;
  if maxi<>v then
  begin
    swap(v,maxi);

    sift(v,m);
  end;
end;


procedure heapsort;
begin
  for i:=m div 2 downto 1 do sift(i,m);
end;


begin

  readln(m);
  read(k);
  while k<>-1 do
  begin
    inc(n);
    num[n]:=k;read(k);
  end;
  for i:=1 to m do
  begin
    f[i]:=num[i];
    id[i]:=i;g[i]:=i;
  end;
  heapsort;
  writeln(f[1]);

  for i:=1 to n-m do
  begin
    k:=id[i];id[i]:=-1;
    f[k]:=num[i+m];id[i+m]:=k;g[k]:=i+m;
    sift(k,m);
    while (k>1) and (f[k]>f[k div 2])do
    begin
      swap(k,k div 2);
      k:=k div 2;
    end;
    writeln(f[1]);
  end;
end.

Tests for this probel are very weak.
Here it is code, that gets AC sn 0.488
you must have weak tests or very good computers=)
[code]
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;
#define pb push_back

int i,j,a,b,n,m,k;
vector <int> mas;

int main()
{
    scanf("%d",&m);
    scanf("%d",&a);
    n=0;
    mas.clear();
    while (a!=-1)
    {
          mas.pb(a);
          scanf("%d",&a);
          n++;
    }
    for (i=0;i<n-m+1;i++)
    {
        printf("%d\n",*max_element(mas.begin()+i,mas.begin()+i+m));
    }
}
[/code]
So in my opinion you should add a test like this:
14000
1
2
3
...
25000
-1

or if even this program can pass it - decrease timelimit..thanks

It is said in problem text that the number of measurings does not exceed 25001. But my program get AC only if I set this number >=25002, else WA#9!!! Check your test please!!! This problem appeared after rejudgement.

"The number of measurements doesn't exceed 25000."

Test 2 has 25001 measurements.

I know AC solution with complexity M * (N - M). Worst case for this solution is when all numbers are in decreasing order. Is there such test in the set?

I don't know why WA. :-(

Could you kindly give me the test#2? Thanks a lot.