Cod sursa(job #246570)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 21 ianuarie 2009 09:15:55
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int x[50011],v[500011],k,n,i,p,q,m,a,b,max=-50000,st;
char ch[500001<<3];
int main(){
freopen("secventa.in","r",stdin);
scanf ("%d %d\n",&n,&k);
gets(ch);
v[1]=atoi(strtok(ch," \n"));
for(i=2;i<=n;i++)
        v[i]=atoi(strtok(NULL," \n"));
//for(i=1;i<=n;i++)
  //    scanf("%d",&v[i]);

x[1]=1;
p=1;q=1;
for(i=2;i<=n;i++)
        {while(x[p]<i-k+1) p++;

        while(v[i]<v[x[q]]  &&  p<=q)

                q--;
        q++;
        x[q]=i;
        if(i==k)
                {max=v[x[1]];st=1;}
        else
        
        if(v[x[p]]>max&&i>k)
                {max=v[x[p]];
                st=i-k+1 ;
                }
       }
FILE *g=fopen("secventa.out","w");
fprintf(g,"%d %d %d",st,(st+k-1),max);
fclose(g);
return 0;}