Cod sursa(job #343755)

Utilizator aladinaladin aladinn aladin Data 27 august 2009 10:19:10
Problema Secventa Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
using namespace std;
#include <cstdio>
#include <deque>
#define N 500009

deque <int> D;

int main()
{int n,k,v[N],i,max=-N,q,st=0,stp=1;
 char s[N*7];

 freopen ("secventa.in","r",stdin);
 freopen("secventa.out","w",stdout);
 scanf("%d %d\n",&n,&k);
 fgets(s,N*7,stdin);
 q=strlen(s);n=0;
 for (i=0;i<=q;++i)
	if (s[i]=='-') stp=-1; else
        if ((s[i]>='0')&& (s[i]<='9'))
            st=st*10+s[i]-'0'; else
                {n++;v[n]=stp*st;
				 stp=1;st=0;}
 D.push_back(1);
 for (i=2;i<=n;++i)
 { scanf("%d",&v[i]);
    while (!D.empty() && D.front()<=i-k) 
		D.pop_front();
	while (!D.empty() && v[D.back()]>v[i])
	    D.pop_back();
	D.push_back(i);
    if ((i>=k) && (v[D.front()]>max)) 
      {max=v[D.front()];st=i-k+1;stp=i;}
}
printf("%d %d %d",st,stp,max);
return 0;}