Cod sursa(job #626693)

Utilizator sebii_cSebastian Claici sebii_c Data 27 octombrie 2011 22:16:07
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.41 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, sign=1;
    int max = -32000;
    char buffer[1040];
    scanf("%d %d", &N, &K);
    fgets(buffer, 1024, stdin);
    for (i=0, ind = 0; i<=N; ) {
	sign = 1, x = 0;
	buffer[strlen(buffer)] = ' ';
	if (buffer[ind] == ' ') {
	    if (++ind == 1024) {
		fgets(buffer, 1024, stdin);
		ind = 0;
	    }
	    continue;
	}   
	if (buffer[ind] == '-') {
	    sign = -1;
	    if (++ind == 1024) {
		fgets(buffer, 1024, stdin);
		ind = 0;
	    }
	}
	while (buffer[ind]>='0' && buffer[ind]<='9') {
	    x = x*10+(buffer[ind]-'0');
	    if (++ind == 1024) {
		fgets(buffer, 1024, stdin);
		ind = 0;
	    }
	}
	x = x*sign;
	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;
}