Cod sursa(job #65143)

Utilizator scapryConstantin Berzan scapry Data 7 iunie 2007 11:40:41
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum { maxn = 500001, inf = 0x3F3F3F3F };

int n, len;
int p[maxn];
int best, best_start, best_end;
int start, end;
int deq[maxn];
int pos[maxn]; //pos of deq[i] in p[]

void go()
{
	int i, seqstart;

	best = -inf;

	for(i = 0; i < n; i++)
	{
		//pop_back() until it's the maximum
		while(end > start && deq[end - 1] > p[i])
			end--;

		//add p[i]
		deq[end] = p[i];
		pos[end] = i;
		end++;

		//pop_front() until pos[end] - pos[start] is short enough
		while(start < end && pos[end - 1] - pos[start] >= len)
			start++;

		//the sequence may start anywhere between the previous-to-start minimum and start
		if(start > 0)
			seqstart = pos[start - 1] + 1;
		else
			seqstart = 0;

		//update ans
		if(pos[end - 1] - seqstart >= len - 1 && deq[start] > best)
		{
			best = deq[start];
			best_start = seqstart;
			best_end = seqstart + len - 1;
		}
	}
}

int main()
{
	int i;
	char buf[maxn * 7], *s = buf;
	size_t stupid_getline = maxn * 7 - 1;
	FILE *f = fopen("secventa.in", "r");
	if(!f) return 1;

	fscanf(f, "%d %d\n", &n, &len);
	getline(&s, &stupid_getline, f);

	for(i = 0; i < n; i++)
	{
		if(i != 0) s++; //the space
		p[i] = atoi(s);
		s = strchr(s, ' ');
	}

	fclose(f);
	f = fopen("secventa.out", "w");
	if(!f) return 1;

	go();

	fprintf(f, "%d %d %d\n", best_start + 1, best_end + 1, best);
	fclose(f);
	return 0;
}