Cod sursa(job #626674)

Utilizator sebii_cSebastian Claici sebii_c Data 27 octombrie 2011 21:29:22
Problema Secventa Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <stdio.h>
#define NMAX 500010

int deque[NMAX];
int A[NMAX];
int N, K;

inline int min(int a, int b)
{
    return (a<b)?a:b;
}

int main()
{
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
    int i, start, stop;
    int max = -32000;
    scanf("%d %d", &N, &K);
    for (i=1; i<=N; ++i)
	scanf("%d", &A[i]);
    int front = 1, back = 0;
    for (i=1; i<=N; ++i) {
	while (front <= back && A[i] <= A[deque[back]])
	    --back;
	deque[++back] = i;
	if (deque[front] == i-K)
	    ++front;
	if (i >= K) {
	    if (A[deque[front]] > max) {
		max = A[deque[front]];
		stop = i;
		start = i-K+1;
	    }
	    else if (A[deque[front]] == max) {
		stop = min(i, stop);
		start = min(i-K+1, start);
	    }
	}
    }
    printf("%d %d %d", start, stop, max);
    return 0;
}