Cod sursa(job #65140)

Utilizator scapryConstantin Berzan scapry Data 7 iunie 2007 11:12:59
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <assert.h>
#include <stdio.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++;

		assert(end > 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;
		}
	}

	assert(best != -inf);
}

int main()
{
	int i;
	FILE *f = fopen("secventa.in", "r");
	if(!f) return 1;

	fscanf(f, "%d%d", &n, &len);
	for(i = 0; i < n; i++)
		fscanf(f, "%d", &p[i]);

	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;
}