Cod sursa(job #135831)

Utilizator allynaAlina S allyna Data 14 februarie 2008 17:38:10
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<fstream.h>
#include<stdlib.h>
long n,i,k,max,s1,s2,p1,p2;
long a[500001],x[500001],poz[500001];
char *s,c[10000000];
int main(void)
{
ifstream in("secventa.in");
ofstream out("secventa.out");
in>>n>>k;
gets(c);
gets(c);
s=c;
for(i=1;i<n;i++)
		{
		a[i]=atol(s);
		s=strchr(s,' ');
		s++;
		}
		a[n]=atol(s);
max=-32000;
x[1]=x[1];
poz[1]=1;
s1=1;
s2=1;
for(i=2;i<=n;i++)
{
	while(s1<=s2&&poz[s1]<=i-k)
		s1++;
	while(s1<=s2&&x[s2]>=a[i])
		s2--;
	s2++;
	x[s2]=a[i];
	poz[s2]=i;
	if(i>=k&&x[s1]>max)
		{
		max=x[s1];
		p2=i;
		p1=p2-k+1;
		}
}
in.close();
out<<p1<<p2<<max;
return 0;
}