Cod sursa(job #59486)

Utilizator scapryConstantin Berzan scapry Data 9 mai 2007 14:29:58
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 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;

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

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

		/*
		//debug
		printf("p[%d] %d. deq: ", i, p[i]);
		assert(end > start);
		for(int i = start; i < end; i++)
		{
			printf("%d (pos %d), ", deq[i], pos[i]);
			assert(p[ pos[i] ] == deq[i]);
		}
		printf("\b\b \b\n");
		*/

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

			//printf("updated best to %d, start %d end %d\n", best, best_start, best_end);
		}
	}

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