Cod sursa(job #65124)

Utilizator scapryConstantin Berzan scapry Data 7 iunie 2007 10:02:05
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <assert.h>
#include <stdio.h>

#define printf(...) /* shut up */

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\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);
		}
		else if(end - 1 == start && i >= len - 1 && p[i] > best)
		{
			//no maximums so far => everything before me is bigger => I'm the minimum
			best = p[i];
			best_start = i - len + 1;
			best_end = i;

			printf("funky shit best %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;
}