Cod sursa(job #809736)

Utilizator vld7Campeanu Vlad vld7 Data 8 noiembrie 2012 22:23:12
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 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 = 1, inc = 1, sf, rez = -(1 << 30);

void read()
{
	fscanf (f, "%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
		fscanf (f, "%d", &a[i]);
}

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 (a[i] < rez)
			inc = i;
		
		if (i - inc + 1 > k && front < back && a[deque[front]] < a[deque[front + 1]]) {
			front++;
			inc++;
		}
		
		if (i - inc + 1 >= k)
			if (a[deque[front]] > rez) {
				rez = a[deque[front]];
				begin = inc;
				sf = i;
			}
	}
}

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