Cod sursa(job #809765)

Utilizator vld7Campeanu Vlad vld7 Data 8 noiembrie 2012 23:22:34
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>

#define maxN 500005

FILE *f = fopen ("secventa.in","r");
FILE *g = fopen ("secventa.out","w");

int n, k, a[maxN], deque[maxN], begin, end, rez = -(1 << 30);
char s[maxN * 7];

void read()
{
	int cnt = 0, x = 0, semn = 1;
	
	fscanf (f, "%d%d\n", &n, &k);
	fgets (s, maxN * 7, f);
	for (int i = 0; s[i] != '\0'; i++)
		if (s[i] >= '0' && s[i] <= '9')
			x = x * 10 + s[i] - '0';
		else if (s[i] == '-')
			semn = -1;
		else {
			a[++cnt] = semn * x;
			x = 0;
			semn = 1;
		}
}

void solve()
{
	int front = 1, back = 0;
	
	for (int i = 1; i <= n; i++) {
		while (front <= back && a[i] <= a[deque[back]])
			back--;
		
		deque[++back] = i;
		
		if (deque[front] == i - k)
			front++;
		
		if (i >= k) {
			if (a[deque[front]] > rez) {
				rez = a[deque[front]];
				begin = i - k + 1;
				end = i;
			}
		}
	}
}

int main()
{
	read();
	solve();
	
	fprintf (g, "%d %d %d\n", begin, end, rez);
	
	fclose(f);
	fclose(g);
	
	return 0;
}