Cod sursa(job #211222)

Utilizator plastikDan George Filimon plastik Data 1 octombrie 2008 13:09:10
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
// http://infoarena.ro/problema/secventa

#include <cstdio>
#include <climits>

/*#include <deque>
using namespace std;

deque<int> Min;*/
int Min[500001];

int n, k, A[500001];

int ans, ansPos;

#define DONE

int main() {
	
	freopen("secventa.in", "r", stdin);
#ifdef DONE
		freopen("secventa.out", "w", stdout);
#endif
	
	scanf("%d %d", &n, &k);
	int i;
	for (i = 0; i < n; ++ i)
		scanf("%d", &A[i]);
	
	ans = INT_MIN, ansPos = -1;
	//deque<int>::iterator di;
	int ds = 0, de = -1;
	
	for (i = 0; i < n; ++ i) {
		if (de >= ds && i >= Min[ds] + k)
			++ ds;
		
		if (de < ds || A[i] > A[Min[de]]) {
			Min[++ de] = i;
		} else {
			while (de >= ds && A[i] < A[Min[de]])
				-- de;
			Min[++ de] = i;
		}
		
		/*for (int j = ds; j <= de; ++ j)
			printf("%d ", A[Min[j]]);
		printf("\n");*/
		
		
		if (i >= k - 1 && ans < A[Min[ds]]) {
			ans = A[Min[ds]];
			ansPos = i;
		}
	}
	
	printf("%d %d %d\n", ansPos - k + 2, ansPos + 1, ans);
	
	return 0;
}