Cod sursa(job #211219)

Utilizator plastikDan George Filimon plastik Data 1 octombrie 2008 13:02:53
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 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 = 0;
	
	for (i = 0; i < n; ++ i) {
		if (de - ds > 0 && i >= Min[ds] + k)
			++ ds;
		
		if (de - ds == 0 || A[i] > A[Min[de]]) {
			Min[++ de] = i;
		} else {
			while (de - ds > 0 && A[i] < A[Min[de]])
				-- de;
			Min[++ de] = i;
		}
		
		/*for (di = Min.begin(); di != Min.end(); ++ di)
			printf("%d ", A[*di]);
		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;
}