Cod sursa(job #129795)

Utilizator TociToxAnonim Anonim TociTox Data 30 ianuarie 2008 11:18:26
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <stdio.h>   
#include <math.h>   
#include <string.h>   
#include <ctype.h>   
  
#define MAXN 500010   
  
long a[MAXN], n, k;   
char st[MAXN * 7];   
long deq[MAXN], start, final;   
  
inline void insert(long value) {   
    while (final >= start && deq[final] > value) {   
        --final;   
    }   
    deq[++final] = value;   
}   
  
inline void del(long value) {   
    if (deq[start] == value) {   
        ++start;   
    }   
}   
  
int main() {   
    long i, na, p = 0, ok = 0, semn = 1, max = 0, poz_st = 0;   
    freopen("secventa.in", "r", stdin);   
    freopen("secventa.out", "w", stdout);   
    scanf("%ld %ld\n", &n, &k);   
    fgets(st, MAXN * 7, stdin);   
    na = 0;   
    for (i = 0; st[i] != 0; ++i) {   
        if (st[i] == '-') {   
            semn = -1;   
            continue;   
        }   
        if (isdigit(st[i])) {   
            p = p * 10 + (long)(st[i] - '0');   
            ok = 1;   
        } else {   
            a[++na] = p * semn;   
            p = 0;   
            semn = 1;   
            ok = 0;   
        }   
    }   
    if (ok) {   
        a[++na] = p;   
        p = 0;   
    }   
       
    //deque   
    for (i = 1; i <= k; ++i) {   
        insert(a[i]);   
    }   
       
    max = deq[start];   
    poz_st = 1;   
       
    for (i = k + 1; i <= n; ++i) {   
        del(a[i - k]);   
        insert(a[i]);   
        if (max < deq[start]) {   
            max = deq[start];   
            poz_st = i - k + 1;   
        }   
    }   
    printf("%ld %ld %ld\n", poz_st, poz_st + k - 1, max);   
    return 0;   
}