Cod sursa(job #211210)

Utilizator plastikDan George Filimon plastik Data 1 octombrie 2008 12:41:16
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
// http://infoarena.ro/problema/secventa

#include <cstdio>

#include <deque>
using namespace std;

deque<int> Min;
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 = 0, ansPos = -1;
	deque<int>::iterator di;
	
	for (i = 0; i < n; ++ i) {
		if (i >= Min.front() + k)
			Min.pop_front();
		
		if (Min.empty() || A[i] > A[Min.back()]) {
			Min.push_back(i);
		} else {
			while (Min.empty() == false && A[i] < A[Min.back()])
				Min.pop_back();
			Min.push_back(i);
		}
		
		/*for (di = Min.begin(); di != Min.end(); ++ di)
			printf("%d ", A[*di]);
		printf("\n");*/
		
		if (i >= k - 1 && ans < A[Min.front()]) {
			ans = A[Min.front()];
			ansPos = i;
		}
	}
	
	printf("%d %d %d\n", ansPos - k + 2, ansPos + 1, ans);
	
	return 0;
}