Cod sursa(job #626695)

Utilizator sebii_cSebastian Claici sebii_c Data 27 octombrie 2011 22:20:54
Problema Secventa Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <stdio.h>
#include <string.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, x, ind;
    int max = -32000;
    char buffer[1<<22];
    scanf("%d %d\n", &N, &K);
    fgets(buffer, 1<<22, stdin);
    for (i=1, ind = 0; i<=N; ++ind, ++i ) {
	if (buffer[ind] == '-') {
	    for (x=0, ++ind ;buffer[ind]>='0' && buffer[ind]<='9'; ++ind)
		x = x*10+(buffer[ind]-'0');
	    A[i] = x*(-1);
	}
	else {
	    for (x=0 ;buffer[ind]>='0' && buffer[ind]<='9'; ++ind)
		x = x*10+(buffer[ind]-'0');
	    A[i] = x;
	}
    }

    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;
}