Cod sursa(job #590310)

Utilizator maritimCristian Lambru maritim Data 16 mai 2011 18:58:04
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>
#include<ctype.h>

long int n;
long int k;
int a;
int semn;
int Deck[500001];
int P[500001];
int Front = 1;
char S[10000001];
long int Back = 0;
long int mar = -30001;
long int poz;

void citire(void)
{
	P[0] = 1;
	int j = -1;
	for(int i=1;i<=n;i++)
	{
		a = 0; semn = 1;
		while(S[++j] == ' ');
		if(S[j] == '-') semn = -1, ++j;
		while(isdigit(S[j]))
		{
			a *= 10;
			a += S[j++] - '0';
		}
		a *= semn;
		Back ++;
		while(Back>=Front && Deck[--Back]>a);
		Deck[++Back] = a;
		P[Back] = i;
		if(P[Front]<=i-k)
			Front ++;
		if(P[Back] >= k && Deck[Front]>mar)
		{
			poz = P[Front-1] + 1;
			mar = Deck[Front];
			if(poz>i-k)
				poz = i-k+1;
		}
	}
}

int main()
{
	FILE *f = fopen("secventa.in","r");
	FILE *g = fopen("secventa.out","w");
	
	fscanf(f,"%d %d\n",&n,&k);
	fgets(S,sizeof(S),f);
	citire();
	fprintf(g,"%d %d %d",poz,poz + k-1,mar);
	
	fclose(f);
	fclose(g);
	return 0;
}