Cod sursa(job #314893)

Utilizator tibiletsKoos Tiberiu Iosif tibilets Data 13 mai 2009 16:17:05
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>
int N,K;
short v[500001],d[500001],p[500001],bm=-32001,in=1,sf=1,b,i,j,n,m=1,di=1,ds=1;//in,sf - pt secventa, di,ds - pt deque
char s[3500001];
void sub()
{for(;v[i]<=d[ds]&&ds>0;ds--);
 d[++ds]=v[i];
 p[ds]=i;}
int main()
{FILE *f=fopen("secventa.in","r"),*g=fopen("secventa.out","w");
fscanf(f,"%d %d",&N,&K);
fgets(s,2,f);fgets(s,3500001,f);
for(;j<N;++i)//++i sare peste spatiul dintre numere
{if(s[i]=='-'){m=-1;++i;}
 while(s[i]>='0'&&s[i]<='9'){n=n*10+(s[i]-'0');++i;}
 v[++j]=n*m;m=1;n=0;}
 d[1]=v[1];p[1]=1;
 for(i=2;i<=K-1;++i)
  sub();
 for(i=K;i<=N;++i)
 {for(;i-p[di]>=K;di++);
  b=v[i];
  if(d[di]<b)b=d[di];
  if(b>bm)
  {bm=b;
   in=i-K+1;
   sf=i;}
  sub();
  if(di>ds)di=ds;
 }
fprintf(g,"%d %d %d",in,sf,bm);
return 0;
}