Cod sursa(job #1473912)

Utilizator dorumusuroiFMI - Doru Musuroi dorumusuroi Data 20 august 2015 14:43:25
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <cstdio>
#include <cstring>
using namespace std;
#define Max(a, b) (a) > (b)? (a):(b)
const char iname[] = "secventa.in";
const char oname[] = "secventa.out";
const int MAXN = 500005;
const int MINVAL = -30005;
const int MAXVAL =  30005;
int A[MAXN], Deque[MAXN], n, k, maxbase = MINVAL;
char buffer[6*MAXN];

void read(){
    freopen(iname, "r", stdin);
    scanf("%d %d\n", &n, &k);
    fgets(buffer, sizeof(buffer), stdin);
    int ind = 1, sign = 1, sizebf = strlen(buffer);
    for(int i = 0; i < sizebf; ++i){
        if(buffer[i]=='-') sign = -1;
        else if(buffer[i] >= '0' && buffer[i] <= '9')
            A[ind]= A[ind]*10 + (buffer[i]-'0');
            else A[ind++]*=sign, sign = 1;
    }
}

int main()
{
    freopen(oname, "w",stdout);
    read();
    int first = 1, last = 0, st, fn;
    for(int i = 1; i <= n; ++i){
        while(first <= last && Deque[first] <= i-k) first++;
        while(last >= first && A[Deque[last]] >= A[i]) last --;
        Deque[++last] = i;
        if(i>=k && A[Deque[first]] > maxbase){
            maxbase = A[Deque[first]];
            st = i-k+1;
            fn = i;
        }

    }
    printf("%d %d %d", st, fn, maxbase);
    return 0;
}