Cod sursa(job #515118)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 20 decembrie 2010 14:11:24
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <stdio.h>
#define NMAX 500010

int v[NMAX], deq[NMAX];
int n, k;

int main() {
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w" ,stdout);
	scanf("%d%d", &n, &k);
	
	for(int i = 1; i <= n; ++i)
		scanf("%d", &v[i]);
	
	int st = 1, dr = 0;
	for(int i = 1; i <= k; ++i) {
		while(st <= dr && v[deq[dr]] > v[i]) dr--;
		deq[++dr] = i;
	}
	int sol = v[deq[st]], xsol = 1, ysol = k;
	for(int i = k+1; i <= n; ++i){
		while(st <= dr && v[deq[dr]] > v[i]) dr--;
		deq[++dr] = i;
		while(deq[dr] - deq[st] + 1 > k) st++;
		if(v[deq[st]] > sol){
			sol = v[deq[st]];
			xsol = i-k+1;
			ysol = i;
		}
	}
	
	printf("%d %d %d\n", xsol, ysol, sol);
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}