Cod sursa(job #65139)

Utilizator scapryConstantin Berzan scapry Data 7 iunie 2007 11:11:30
Problema Secventa Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 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++;

		{
			//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\n");
		}

		assert(end > start);

		if(start > 0)
			seqstart = pos[start - 1] + 1;
		else
			seqstart = 0;

		printf("seqstart %d\n", seqstart);

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