Cod sursa(job #36426)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 23 martie 2007 16:07:28
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
# include <stdio.h>
# include <string.h>
# include <stdlib.h>

const long int MAXN=500000;
const long int MAXL=MAXN*10;
char s[MAXL+2],*p;
struct {long int poz,val;} deq[MAXN+1];
long int front=1,back=1,n,k,sol,psol;
long int sir[MAXN+1];

void add(long int a, long int poz)
{
long int i=back;
while (i>=front&&deq[i].val>a) i--;
deq[i+1].val=a;
deq[i+1].poz=poz;
back=i+1;
}

void citire()
{
FILE *f=fopen("secventa.in","r");
fscanf(f,"%ld%ld",&n,&k);
long int i;
fgets(s,MAXL-10,f);
fgets(s,MAXL-10,f);
fclose(f);
p=strtok(s," \n");
sir[1]=atoi(p);
for (i=2;i<=n;i++)
	{
	p=strtok(NULL," \n");
	sir[i]=atoi(p);
	}
fclose(f);
for (i=1;i<=k-1;i++)
	add(sir[i],i);
for (i=k;i<=n;i++)
	{
	add(sir[i],i);
	if (deq[front].poz<i-k+1) front++;
	if (deq[front].val>sol||i==k)
		{
		sol=deq[front].val;
		psol=i-k+1;
		}
	}
}

void scrie()
{
FILE *g=fopen("secventa.out","w");
fprintf(g,"%ld %ld %ld\n",psol,psol+k-1,sol);
fcloseall();
}

int main()
{
citire();
scrie();
return 0;
}