Cod sursa(job #645677)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 10 decembrie 2011 12:13:29
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<cstdio>
#include<cstring>
#define N 500001
#define M 3500001
int n,i,r[N],p=1,u=1,k,a,b,v[N],s=-30001,m,w,j=1;
char t[M];
int main()
{FILE *f=fopen("secventa.in","r"),*g=fopen("secventa.out","w");
fscanf(f,"%d%d\n",&n,&k);
fgets(t,M,f),m=strlen(t)-1;
puts(t);
for(i=0;i<m;i++)
if(t[i]>='0'&&t[i]<='9')
       {v[j]=v[j]*10+(t[i]-'0');
       if(t[i+1]==' ')
               v[j]=w*v[j];}
else
       if(t[i]=='-')
               w=-1;
       else
               w=1,j++;
for(i=1;i<=n;i++)
       {while(p<=u&&r[p]<=i-k&&v[r[p]]<=v[r[p+1]])
              p++;
       while(p<=u&&v[i]<=v[r[u]])
              u--;
       r[++u]=i;
       if(i>=k&&v[r[p]]>s)
              s=v[r[p]],a=i-k+1,b=i;}
fprintf(g,"%d %d %d",a,b,s);
return 0;}