Cod sursa(job #130251)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 31 ianuarie 2008 18:04:36
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 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;  
 }